题解 P1436 【棋盘分割】
Zesty_Fox
2020-01-30 14:28:32
嗯，点开题目，哇！是一道~~闪亮亮~~的蓝题!
不要被吓到了，其实，这道题就是一个简单的DP啦!
我们设 $f[x1][y1][x2][y2][c]$ 为以 $(x1,y1)$ 为左上角，以 $(x2,y2)$ 为右下角的矩形分割成c个部分所取得的最大分数。
枚举每一行（列），将其分割成两部分，然后考虑是继续分割上（左）边还是下（右）边
所以，转移方程就出来啦！
$f[x1][y1][x2][y2][c]=\min(\min(f[x1][y1][x][y2][c-1]+sum[x+1][y1][x2][y2]^2,f[x+1][y1][x2][y2][c-1]+sum[x1][y1][x][y2]^2) ,$
$\min(f[x1][y1][x2][y][c-1]+sum[x1][y+1][x2][y2]^2,f[x1][y+1][x2][y2][c-1]+sum[x1][y1][x2][y]^2))$
$(x1 \leq x < x2,y1 \leq y < y2)$
边界情况:当 $c=1,f[x1][y1][x2][y2][c]=sum[x1][y1][x2][y2]$
最后结果即为 $f[1][1][8][8][c]$
$sum[x1][y1][x2][y2][c]$ 为以 $(x1,y1)$ 为左上角，以 $(x2,y2)$ 为右下角的矩形内的总分数
对 $sum$ 进行预处理，这里要算出二维前缀和，设为 $s[i][j]$
则 $sum[x1][y1][x2][y2]=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]$
好了，就这样，一个完美的DP就出来啦！
（~~也就~~六重循环吗）
欢乐的贴代码时间：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,a[9][9],f[9][9][9][9][16];
int s[9][9],sum[9][9][9][9];
int main(){
memset(f,0x3f,sizeof(f));
scanf("%d",&n);
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
scanf("%d",&a[i][j]);
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
for(int k=i;k<=8;k++){
for(int l=j;l<=8;l++){
sum[i][j][k][l]=s[k][l]-s[i-1][l]-s[k][j-1]+s[i-1][j-1];
f[i][j][k][l][1]=sum[i][j][k][l]*sum[i][j][k][l];
}
}
}
}
for(int c=2;c<=n;c++){
for(int len1=1;len1<=8;len1++){
for(int i=1,j=len1;j<=8;i++,j++){
for(int len2=1;len2<=8;len2++){
for(int k=1,l=len2;l<=8;k++,l++){
int x1=i,y1=k,x2=j,y2=l;
for(int row=x1;row<x2;row++){
f[x1][y1][x2][y2][c]=min(min(f[x1][y1][x2][y2][c],\
f[x1][y1][row][y2][c-1]+sum[row+1][y1][x2][y2]*sum[row+1][y1][x2][y2]),\
f[row+1][y1][x2][y2][c-1]+sum[x1][y1][row][y2]*sum[x1][y1][row][y2]);
}
for(int col=y1;col<y2;col++){
f[x1][y1][x2][y2][c]=min(min(f[x1][y1][x2][y2][c],\
f[x1][y1][x2][col][c-1]+sum[x1][col+1][x2][y2]*sum[x1][col+1][x2][y2]),\
f[x1][col+1][x2][y2][c-1]+sum[x1][y1][x2][col]*sum[x1][y1][x2][col]);
}
}
}
}
}
}
printf("%d\n",f[1][1][8][8][n]);
return 0;
}
```
本人蒟蒻，求大佬指教~~~~