题解 P1436 【棋盘分割】 搜索

2018-07-11 15:44:45


博客传送门

五维DP真的不敢想啊这是一张图片

题目一看上去:两边只选一边分,二叉树?但是可以沿着任何一条边分,状态太多不好处理。于是试着搜索,权值和用二维前缀和优化。

   因为棋盘固定为8×8,所以对于初始状态,枚举1~7行(作为上半边最下一行),再枚举分上半边还是下半边,如果选择一半,就计算另一半权值和的平方,加入$sum$,dfs另一半。还要枚举1~7列,dfs枚举左半边和右半边。

   由此可以推到一般情况,dfs带入左上角坐标$(lx,ly)$、右下角坐标$(rx,ry)$确定一个矩形。枚举$[lx,ry)$行,与上面做相同的操作,各计算两边的权值和平方(一边dfs出来后算另一边时记得减掉),另一边带入dfs。

   当dfs进行到第$n$次时,就终止过程(要在函数开始时判断,不能执行第$n$次)。此时计算当前矩形权值和的平方,加入$sum$,与答案进行比较取较小值。

剪枝:

   最优解剪枝:这个搜索只用这一个剪枝就可以把代码从50分优化到100分,当目前$sum$大于已经计算出来的$minn$时,直接返回。

Code:

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
int b[10][10];
int minn=0x3fffffff;
int cal(int lx,int ly,int rx,int ry)//计算前缀和
{
    return b[rx][ry]-b[lx-1][ry]-b[rx][ly-1]+b[lx-1][ly-1];
}
int sum=0,n;
void dfs(int k,int lx,int ly,int rx,int ry)
{
    if(sum>minn)
        return;
    if(k+1==n)
    {
        int now=cal(lx,ly,rx,ry);
        now*=now;//最后加上这一矩阵的平方
        minn=min(sum+now,minn);
        return;
    }
    //枚举从第i行切
    for(int i=lx;i<rx;i++)
    {
        int half=cal(i+1,ly,rx,ry)*cal(i+1,ly,rx,ry);
        sum+=half;
        dfs(k+1,lx,ly,i,ry);
        sum-=half;
        half=cal(lx,ly,i,ry)*cal(lx,ly,i,ry);
        sum+=half;
        dfs(k+1,i+1,ly,rx,ry);
        sum-=half;
    }
    //枚举从第i列切
    for(int i=ly;i<ry;i++)
    {
        int half=cal(lx,i+1,rx,ry)*cal(lx,i+1,rx,ry);
        sum+=half;
        dfs(k+1,lx,ly,rx,i);
        sum-=half;
        half=cal(lx,ly,rx,i)*cal(lx,ly,rx,i);
        sum+=half;
        dfs(k+1,lx,i+1,rx,ry);
        sum-=half;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
        {
            scanf("%d",&b[i][j]);
            b[i][j]+=b[i-1][j]+b[i][j-1];
            b[i][j]-=b[i-1][j-1];
        }
    sum=0;
    dfs(0,1,1,8,8);//初态
    printf("%d\n",minn);
    return 0;
}