其实呢大致思路和下面的大佬们都很像。
发这篇题解的目的就是加了一点~~优化~~骗分技巧。
转移方程：
设$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[][];//存图，价值
int sum[][];//前缀和数组
int dp[][][][][];//dp暴力数组
inline void add(int i,int j)
{
//这个函数是计算前缀和数组。左上(1,1)右下(i,j)的价值
//好好想想为什么。（扩展这个点时左边矩形+右边矩形-重叠的部分+这个点的价值）
sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+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-]-sum[x1-][y2]+sum[x1-][y1-];
return now;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=;i++)
for(int j=;j<=;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=;i<=;i++)
for(int j=;j<=;j++)
for(int x=i;x<=;x++)
for(int y=j;y<=;y++)
dp[i][j][x][y][]+=s(i,j,x,y),
dp[i][j][x][y][]*=dp[i][j][x][y][];
//dp过程，深吸一口气读完这一面方程。
for(int k=;k<n;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int x=i;x<=;x++)
for(int y=j;y<=;y++)
{
int minn=0x3f3f3f3f;
for(int a=j;a<y;a++)
minn=min(minn,min(dp[i][j][x][a][k-]+dp[i][a+][x][y][],dp[i][j][x][a][]+dp[i][a+][x][y][k-]));
for(int b=i;b<x;b++)
minn=min(minn,min(dp[i][j][b][y][k-]+dp[b+][j][x][y][],dp[i][j][b][y][]+dp[b+][j][x][y][k-]));
dp[i][j][x][y][k]=minn;
}
printf("%d",dp[][][][][n-]);
//输出，程序拜拜。
return ;
}