其实呢大致思路和下面的大佬们都很像。
发这篇题解的目的就是加了一点~~优化~~骗分技巧。
转移方程：
设$dp[i][j][x][y][k]$表示左上$(i,j)$，右下$(x,y)$，第$k$次割的最大面积。
则对于
$\sum_{k=1}^{n}$
开始更新，有：(~~一口气读完这个方程~~)
$\sum_{i=1}^{8} \sum_{j=1}^{8} \sum_{x=1}^{8} \sum_{y=1}^{8}$
$a=j……y-1;b=i……x-1;$
$dp[i][j][x][y][k]=$
$min($
$min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1]),$
$min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1])$
$);$
但是。
别以为推出了方程就万事大吉了！！！
您的边界条件呢（这题~~很简单~~）。
但是这题的初始化是重点！！！重点！！！重点！！！
好几篇都是6重循环暴力算的。
本宝宝：前缀和先求出来就好了。
那么好，初始化的话是要把所有左上为$(i,j)$右上为$(x,y)$,割了0次的面积求出来。这里，本宝宝用了一个前缀和的思想和容斥原理。
先在输入的时候就处理出来所有左上$(1,1)$右上$(i,j)$的得分（前缀和）；
然后利用容斥原理（具体见代码）
能少些~~三~~两个循环呢。。。
上代码（码风不好请原谅）
//by Su Qingnian //QAQ #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n;//n是总共切的刀数 int map[9][9];//存图，价值 int sum[9][9];//前缀和数组 int dp[9][9][9][9][15];//dp暴力数组 inline void add(int i,int j) { //这个函数是计算前缀和数组。左上(1,1)右下(i,j)的价值 //好好想想为什么。（扩展这个点时左边矩形+右边矩形-重叠的部分+这个点的价值） sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j]; return ; } inline int s(int x1,int y1,int x2,int y2) { //这个是用来计算左上(x1,y1)右下(x2,y2)的价值 //还是容斥原理 int now=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; return now; } int main() { scanf("%d",&n); for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) scanf("%d",&map[i][j]), add(i,j);//输入，处理前缀和 //debug // for(int i=1;i<=8;i++,puts("")) // for(int j=1;j<=8;j++) // printf("%-5d ",sum[i][j]); //处理切0刀时各矩形价值的平方 for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) for(int x=i;x<=8;x++) for(int y=j;y<=8;y++) dp[i][j][x][y][0]+=s(i,j,x,y), dp[i][j][x][y][0]*=dp[i][j][x][y][0]; //dp过程，深吸一口气读完这一面方程。 for(int k=1;k<n;k++) for(int i=1;i<=8;i++) for(int j=1;j<=8;j++) for(int x=i;x<=8;x++) for(int y=j;y<=8;y++) { int minn=0x3f3f3f3f; for(int a=j;a<y;a++) minn=min(minn,min(dp[i][j][x][a][k-1]+dp[i][a+1][x][y][0],dp[i][j][x][a][0]+dp[i][a+1][x][y][k-1])); for(int b=i;b<x;b++) minn=min(minn,min(dp[i][j][b][y][k-1]+dp[b+1][j][x][y][0],dp[i][j][b][y][0]+dp[b+1][j][x][y][k-1])); dp[i][j][x][y][k]=minn; } printf("%d",dp[1][1][8][8][n-1]); //输出，程序拜拜。 return 0; }
