P1436 棋盘分割
分析
考虑多维的dp
dp[a][b][c][d][k]
将矩形[a,b][c,d]表示划分k次得到的最大值
明显答案即为dp[1][1][8][8][k]
初始状态为dp[i][j][ii][jj][1]=矩阵和的平方
转移方程：
枚举i<=x
就是把矩阵横着分为两半
同理枚举y
点击查看代码
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define inf 0x7fffffff
ll dp[10][10][10][10][20];
ll a[10][10];
int n;
void init(){
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
a[i][j]+=a[i][j-1];
for(int j=1;j<=8;j++)
for(int i=1;i<=8;i++)
a[i][j]+=a[i-1][j];
}
ll find(int x1,int y1,int x2,int y2){
return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
ll p(ll a){
return a*a;
}
void dd(){
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][1]=p(find(i,j,x,y));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
scanf("%d",&a[i][j]);
init();dd();
for(int k=2;k<=n;k++)
for(int x1=1;x1<=8;x1++)
for(int y1=1;y1<=8;y1++)
for(int x2=x1;x2<=8;x2++)
for(int y2=y1;y2<=8;y2++){
dp[x1][y1][x2][y2][k]=1<<30;
for(int i=x1;i