题解 P1436 【棋盘分割】 搜索

博客[传送门](http://www.wjyyy.top/821.html) 五维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： ```cpp #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; } ```