二维区间dp
棋盘分割
- 将8*8的棋盘分割n次，求所有矩阵里面的数的平方和总和最少
cpp
const int N=10,M=15;
int a[N][N],s[N][N],n;
double f[N][N][N][N][M];//f[x1][y1][x2][y2][k]表示当前块为(x1,y1)~(x2,y2),并且分割了k次的值
double X;
double get(int x1,int y1,int x2,int y2){
double sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]-X;
return sum*sum/n;
}
double dp(int x1,int y1,int x2,int y2,int k){
double &v=f[x1][y1][x2][y2][k];
if(v>=0)return v;
if(k==1)return v=get(x1,y1,x2,y2);
v=1e9;
for(int i=x1;i<x2;i++){
v=min(v,dp(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));
v=min(v,dp(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));
}
for(int i=y1;i<y2;i++){
v=min(v,dp(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));
v=min(v,dp(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i));
}
return v;
}
void solve(){
cin>>n;
for(int i=1;i<=8;i++){
for(int j=1;j<=8;j++){
cin>>a[i][j];
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
}
}
memset(f,-1,sizeof f);
X=(double)s[8][8]/n;
cout<<setprecision(3)<<fixed<<sqrt(dp(1,1,8,8,n));
}