作者在 2008-08-22 12:32:59 发布以下内容
黑书 p116页上有详细的分析
代码
如下:
#include <iostream> #include <math.h> using namespace std; int grid[8][8]; int d[16][9][9][9][9]; int sm[9][9]; int const INF=10000000; int n; int sum(int i,int j,int s,int t) { return sm[s][t]-sm[i][t]-sm[s][j]+sm[i][j]; } int comp(int a,int b,int c) { if(a<=b&&a<=c) return a; else if(b<=c) return b; else return c; } int minn(int k,int i,int j,int s,int t) { int r; int tem1,tem2; int min=INF; for( r=i;r<s;r++) { tem1=d[k][i][j][r][t]+sum(r,j,s,t)*sum(r,j,s,t); tem2=d[k][r][j][s][t]+sum(i,j,r,t)*sum(i,j,r,t); min=comp(min,tem1,tem2); } for( r=j;r<t;r++) { tem1=d[k][i][j][s][r]+sum(i,r,s,t)*sum(i,r,s,t); tem2=d[k][i][r][s][t]+sum(i,j,s,r)*sum(i,j,s,r); min=comp(min,tem1,tem2); } return min; } void input() { int i,j,k,s,t; memset(grid,0,sizeof(grid)); for(k=0;k<=15;k++) for(i=0;i<=8;i++) for(j=0;j<=8;j++) for(s=0;s<=8;s++) for(t=0;t<=8;t++) d[k][i][j][s][t]=INF; cin >>n; for(i=0;i<8;i++) for(j=0;j<8;j++) cin >>grid[i][j]; } void init() { int i,j,s,t; for(i=0;i<=8;i++) { sm[0][i]=0; sm[i][0]=0; } for(i=1;i<=8;i++) { int temp=0; for(j=1;j<=8;j++) { temp+=grid[i-1][j-1]; sm[i][j]=sm[i-1][j]+temp; } } for(i=0;i<=8;i++) for(j=0;j<=8;j++) for(s=i+1;s<=8;s++) for(t=j+1;t<=8;t++) { int tt=sum(i,j,s,t); d[0][i][j][s][t]=tt*tt; } return ; } void dp() { int i,j,k,s,t; for(k=1;k<n;k++) { for(i=0;i<=8;i++) for(j=0;j<=8;j++) for(s=i+1;s<=8;s++) for(t=j+1;t<=8;t++) { d[k][i][j][s][t]=minn(k-1,i,j,s,t); } } } int main() { input(); init(); dp(); printf("%.3lf\n",sqrt(d[n-1][0][0][8][8]*1.0/double(n)-sm[8][8]*sm[8][8]*1.0/double(n*n))); return 0; }