棋盘分割Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 23    Accepted Submission(s): 18 Problem Description 将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行) 原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。 均方差，其中平均值xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出O'的最小值。   Input 第1行为一个整数n(1 < n < 15)。 第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。   Output 仅一个数，为O'（四舍五入精确到小数点后三位）。   Sample Input 3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3   Sample Output 1.633   Source 华东交通大学2008(秋季)ACM程序设计竞赛(公开赛)   Recommend lcy   #include<stdio.h>#include<math.h>int f[8][8];double g[20][8][8][8][8];int main(){ int n,b; int i,j,ii,jj,i1,j1,k; double total=0,res,min; scanf("%d",&n); for(i=0;i<8;i++)  for(j=0;j<8;j++)  {   scanf("%d",&f[i][j]);   total+=f[i][j];  } total=total/(double)n; total=total*total; for(i=0;i<8;i++)  for(j=0;j<8;j++)   for(ii=i;ii<8;ii++)    for(jj=j;jj<8;jj++)    {     g[1][i][j][ii][jj]=0;     for(i1=i;i1<=ii;i1++)      for(j1=j;j1<=jj;j1++)       g[1][i][j][ii][jj]+=f[i1][j1];    g[1][i][j][ii][jj]=g[1][i][j][ii][jj]*g[1][i][j][ii][jj];    } min=1000000; for(k=2;k<=n;k++) {  for(i=0;i<8;i++)   for(j=0;j<8;j++)    for(ii=i;ii<8;ii++)     for(jj=j;jj<8;jj++)     {        min=1000000;      for(b=i;b<ii;b++)      {       if(g[k-1][i][j][b][jj]+g[1][b+1][j][ii][jj]<min)         min=g[k-1][i][j][b][jj]+g[1][b+1][j][ii][jj];       if(g[k-1][b+1][j][ii][jj]+g[1][i][j][b][jj]<min)         min=g[k-1][b+1][j][ii][jj]+g[1][i][j][b][jj];      }      for(b=j;b<jj;b++)      {       if(g[k-1][i][b+1][ii][jj]+g[1][i][j][ii][b]<min)        min=g[k-1][i][b+1][ii][jj]+g[1][i][j][ii][b];       if(g[k-1][i][j][ii][b]+g[1][i][b+1][ii][jj]<min)        min=g[k-1][i][j][ii][b]+g[1][i][b+1][ii][jj];      }      g[k][i][j][ii][jj]=min;     } } res=g[n][0][0][7][7]/n-total; printf("%.3lf\n",sqrt(res)); return 0; }

评论