动态规划：
我们设状态$f[i][j][o][p][k]$表示一个矩形，左上角顶点坐标为$(i,j)$，右下角顶点坐标为$(o,p)$时分割了$k$次，也就是说现在是$k+1$块
我们考虑状态转移：
枚举$ii$为切割某列，那么状态转移如下：
$minn=min(minn,min(f[i][j][o][ii][k-1]+f[i][ii+1][o][p][0],f[i][j][o][ii][0]+f[i][ii+1][o][p][k-1]))$
枚举$ii$为切割某行，那么状态转移如下：
$minn=min(minn,min(f[i][j][ii][p][k-1]+f[ii+1][j][o][p][0],f[i][j][ii][p][0]+f[ii+1][j][o][p][k-1]))$
初始化的时候弄个二维前缀和就好了
代码：
#include<iostream>
#include<cstdio>
#define N 9
#define M 17
using namespace std;
int n;
int g[N][N],sum[N][N],f[N][N][N][N][M];
int main()
{
scanf("%d",&n);
for(int i=1;i<=8;++i)
for(int j=1;j<=8;++j)
scanf("%d",&g[i][j]),sum[i][j]=sum[i-1][j]+sum[i][j-1]+g[i][j]-sum[i-1][j-1];
// for(int i=1;i<=8;++i)
// {
// for(int j=1;j<=8;++j)
// printf("%d ",sum[i][j]);
// printf("\n");
// }
for(int i=1;i<=8;++i)
for(int j=1;j<=8;++j)
for(int o=i;o<=8;++o)
for(int p=j;p<=8;++p)
f[i][j][o][p][0]=sum[o][p]-sum[o][j-1]-sum[i-1][p]+sum[i-1][j-1],f[i][j][o][p][0]*=f[i][j][o][p][0];
for(int k=1;k<n;++k)
for(int i=1;i<=8;++i)
for(int j=1;j<=8;++j)
for(int o=i;o<=8;++o)
for(int p=j;p<=8;++p)
{
int minn=0x3f3f3f3f;
for(int ii=j;ii<p;++ii)
minn=min(minn,min(f[i][j][o][ii][k-1]+f[i][ii+1][o][p][0],f[i][j][o][ii][0]+f[i][ii+1][o][p][k-1]));
for(int ii=i;ii<o;++ii)
minn=min(minn,min(f[i][j][ii][p][k-1]+f[ii+1][j][o][p][0],f[i][j][ii][p][0]+f[ii+1][j][o][p][k-1]));
f[i][j][o][p][k]=minn;
}
printf("%d",f[1][1][8][8][n-1]);
return 0;
}
原文：https://www.cnblogs.com/yexinqwq/p/10207317.html