http://poj.org/problem?id=1191
1>根据公式化简：
其中后者是一个已知数。求均方差的最小值就是求出个个棋盘内各数值的平方和最小值。
2>棋盘分割分四种情况：
竖切（左不动），竖切（右不动），横切（上不动），横切（下不动）；
3>状态转移方程：
f(i, x1, y1, x2, y2)表示以（x1, y1),(x2, y2)为四边形对角线的棋盘切割成i块的各块值总平方的最小值；
D(x1, y1, x2, y2)表示棋盘的总分
_____________
| f(i-1, x1, a+1, x2, y2)+D(x1, y1, x2, a) [横切（上不动）]
| f(i-1, x1,y1, x2, a)+D(x1, a+1, x2, y2) [横切（下不动）]
f(i, x1, y1, x2, y2)=min| f(i-1,b+1, y1, x2, y2)+D(x1, y1, b1, y2) [竖切（左不动）]
| f(i-1, x1, y1, b, y2)+D(b+1, y1, x2, y2) [竖切（右不动）]
______________
4>其中的a, b是进行枚举的值。先预处理D（x1, y1, x2, y2)
代码如下：
View Code
/** * POJ 1191 棋盘分割 */ #include<stdio.h> #include<string.h> #include<math.h> int a[9][9], F[15][9][9][9][9]; int minx(int a1, int a2, int a3) { int minnum=99999999; if(a1<minnum) minnum=a1; if(a2<minnum) minnum=a2; if(a3<minnum) minnum=a3; return minnum; } int get(int x1,int y1,int x2,int y2) //用来计算分割出来块的总分 { return a[x2][y2]-a[x2][y1-1]-a[x1-1][y2]+a[x1-1][y1-1]; } int main() { int n, i, j, x1, y1, x2, y2, aa, b; while(scanf("%d", &n)!=EOF) { memset(F, 0, sizeof(F)); memset(a, 0, sizeof(a)); for(i=1; i<=8; i++) for(j=1; j<=8; j++) { scanf("%d",&a[i][j]); a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]; } for(i=1; i<=n; i++) for(x1=1; x1<=8; x1++) for(y1=1; y1<=8; y1++) for(x2=1; x2<=8; x2++) for(y2=1; y2<=8; y2++) { if(i==1||x1==x2||y1==y2) { F[i][x1][y1][x2][y2]=get(x1, y1, x2, y2)*get(x1, y1, x2, y2); continue; } int t1=99999999; for(aa=y1; aa<y2; aa++) t1=minx(t1, F[i-1][x1][aa+1][x2][y2]+get(x1, y1, x2, aa)*get(x1, y1, x2, aa), F[i-1][x1][y1][x2][aa]+get(x1, aa+1, x2, y2)*get(x1, aa+1, x2, y2)); for(b=x1; b<x2; b++) t1=minx(t1, F[i-1][b+1][y1][x2][y2]+get(x1, y1, b, y2)*get(x1, y1, b, y2), F[i-1][x1][y1][b][y2]+get(b+1, y1, x2, y2)*get(b+1, y1, x2, y2)); F[i][x1][y1][x2][y2]=t1; } double tt=F[n][1][1][8][8]*1.0/n-pow(a[8][8]*1.0/n, 2.0); printf("%.3lf\n", sqrt(tt)); } return 0; }