【POJ1191】棋盘分割 || NYOJ87

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 01 月 10 日

/*POJ1191棋盘分隔,刘汝佳黑书面有解析,大概思路如下:
* 根据方差公式推倒出如果需要方差最小,则需要每个被减数的平方最小,即每块棋盘的总分平方和最小
* 考虑左上角坐标为(x1,y1),右下角坐标为(x2,y2)的棋盘,设它的总和为sum[x1,y1,x2,y2]切割k次以后得到
* k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2],则它可以沿着横线切,也可以沿着竖线切,然后选一
* 块继续切(递归)。。
* 状态转移方程:
* d[k,x1,y1,x2,y2]=min{
* min{d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]^2,d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]^2},
* min{d[k-1,x1,y1,x2,b]+s[x1,b+1,x2,y2]^2,d[k-1,x1,b+1,x2,y2]+s[x1,y1,x2,b]^2}}
* 其中:(x1<=a #include<iostream> #include<cstring> #include<iomanip> #include<cmath> using namespace std; int m[9][9]; int sum[9][9]; int d[15][9][9][9][9]; int needsum(int x1,int y1,int x2,int y2) {return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];} int min(int a,int b) { return a>b?b:a; } int fun(int k,int x1,int y1,int x2,int y2) { int t,a,b,c,e,MIN=10000000; if(d[k][x1][y1][x2][y2] !=-1) return d[k][x1][y1][x2][y2]; if(k==0) { t=needsum(x1,y1,x2,y2); d[k][x1][y1][x2][y2]=t*t; return t*t; } for(a=x1;a<x2;a++) { c=needsum(a+1,y1,x2,y2); e=needsum(x1,y1,a,y2); t=min(fun(k-1,x1,y1,a,y2)+c*c,fun(k-1,a+1,y1,x2,y2)+e*e); if(MIN>t) MIN=t; } for(b=y1;b<y2;b++) { c=needsum(x1,b+1,x2,y2); e=needsum(x1,y1,x2,b); t=min(fun(k-1,x1,y1,x2,b)+c*c,fun(k-1,x1,b+1,x2,y2)+e*e); if(MIN>t) MIN=t; } d[k][x1][y1][x2][y2]=MIN; return MIN; } int main() { memset(sum ,0 ,sizeof(sum)); memset(d ,-1 ,sizeof(d)); int n; cin>>n; for (int i=1;i<9;i++) for (int j=1,rowsum=0;j<9;j++) { cin>>m[i][j]; rowsum +=m[i][j]; sum[i][j] += sum[i-1][j] + rowsum; } double result = n*fun(n-1,1,1,8,8)-sum[8][8]*sum[8][8]; cout<<setiosflags(ios::fixed)<<setprecision(3)<<sqrt(result/(n*n))<<endl; return 0; } /*int fun(int k) { int t,a,b,c,e,d,MIN,i,j,m,n; for(i=1;i<=8;i++) for(j=1;j<=8;j++) for(m=1;m<=8;m++) for(n=1;n<=8;n++) { t=needsum(i,j,m,n); d[0][i][j][m][n]=t*t; } for(a=1;a<=k;a++) for(i=1;i<=8;i++) for(j=1;j<=8;j++) for(m=1;m<=8;m++) for(n=1;n<=8;n++) { MIN=10000000; if((m-i+1)*(n-j+1)<a+1) {d[a][i][j][m][n]=MIN;continue;} for(d=i;d<m;d++) { c=needsum(d+1,j,m,n); e=needsum(i,j,d,n); t=min(d[a-1][i][j][d][n]+c*c,d[a-1][d+1][j][m][n]+e*e); if(MIN>t) MIN=t; } for(b=j;b<n;b++) { c=needsum(i,b+1,m,n); e=needsum(i,j,m,b); t=min(d[a-1][i][j][m][b]+c*c,d[a-1][i][b+1][m][n]+e*e); if(MIN>t) MIN=t; } d[a][i][j][m][n]=MIN; } return d[k][1][1][8][8]; }*/

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日