思路：黑书的例题
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #define Maxn 20 #define mul(a) ((a)*(a)) using namespace std; int dp[16][9][9][9][9]; int s[10][10],val[10][10]; int S(int x1,int y1,int x2,int y2) { return mul(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } int main() { int n,m,i,j; double avg; while(scanf("%d",&n)!=EOF) { memset(dp,70,sizeof(dp)); memset(s,0,sizeof(s)); for(i=1;i<=8;i++) for(j=1;j<=8;j++){ scanf("%d",&val[i][j]); s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+val[i][j]; } int x1,y1,x2,y2; for(x1=1;x1<=8;x1++) for(y1=1;y1<=8;y1++) for(x2=x1;x2<=8;x2++) for(y2=y1;y2<=8;y2++){ dp[0][x1][y1][x2][y2]=S(x1,y1,x2,y2); } int a,b; for(i=1;i<=n-1;i++) for(x1=7;x1>=1;x1--) for(y1=7;y1>=1;y1--) for(x2=x1;x2<=8;x2++) for(y2=y1;y2<=8;y2++){ int temp; for(a=x1;a<x2;a++){ temp=min(dp[i-1][x1][y1][a][y2]+S(a+1,y1,x2,y2),dp[i-1][a+1][y1][x2][y2]+S(x1,y1,a,y2)); dp[i][x1][y1][x2][y2]=min(temp,dp[i][x1][y1][x2][y2]); } for(b=y1;b<y2;b++){ temp=min(dp[i-1][x1][y1][x2][b]+S(x1,b+1,x2,y2),dp[i-1][x1][b+1][x2][y2]+S(x1,y1,x2,b)); dp[i][x1][y1][x2][y2]=min(dp[i][x1][y1][x2][y2],temp); } } double ans; avg=s[8][8]*1.0/(n*1.0); ans=(double)dp[n-1][1][1][8][8]; ans=ans/(n*1.0); ans-=avg*avg; printf("%.3lf ",sqrt(ans)); } return 0; }