poj1191

#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> using namespace std; int n; int sum; int dp[16][9][9][9][9]; int g[9][9][9][9]; int mp[9][9]; double ave; void init(){ sum=0; scanf("%d",&n); for(int i=0;i<8;i++){ for(int j=0;j<8;j++){ scanf("%d",&mp[i][j]); sum+=mp[i][j]; } } ave = sum*1.0/n; for(int x=0;x<9;x++) for(int y=0;y<9;y++){ for(int xx=x;xx<9;xx++) for(int yy=y;yy<9;yy++){ int ans=0; for(int i=x;i<=xx;i++) for(int j=y;j<=yy;j++){ ans+=mp[i][j]; } g[x][y][xx][yy]=ans*ans; } } } int DP(int k,int x,int y,int xx,int yy) { int i,ans=0; if(dp[k][x][y][xx][yy]>=0) return dp[k][x][y][xx][yy]; if(k==n⑴) return g[x][y][xx][yy]; dp[k][x][y][xx][yy]=1<<29; for(i=x;i<xx;i++){ ans=min(DP(k+1,x,y,i,yy)+g[i+1][y][xx][yy],DP(k+1,i+1,y,xx,yy)+g[x][y][i][yy]); dp[k][x][y][xx][yy]=min(ans,dp[k][x][y][xx][yy]); } for(i=y;i<yy;i++){ ans=min(DP(k+1,x,y,xx,i)+g[x][i+1][xx][yy],DP(k+1,x,i+1,xx,yy)+g[x][y][xx][i]); dp[k][x][y][xx][yy]=min(ans,dp[k][x][y][xx][yy]); } return dp[k][x][y][xx][yy]; } int main(){ init(); memset(dp,⑴,sizeof(dp)); DP(0,0,0,7,7); printf("%.3f ",sqrt((dp[0][0][0][7][7])*1.0/n-ave*ave)); return 0; }

#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int n; long double d[16][9][9][9][9]; long double s[9][9][9][9]; double map[9][9]; int count_map[9][9]; long double sum; long double ave; const int m = 8; const double INF = 0x7f7f7f7f; double count(int i,int j,int i2,int j2) { double ans = count_map[i2][j2] - count_map[i2][j⑴] - count_map[i⑴][j2] + count_map[i⑴][j⑴]; return ans*ans; } void init() { int i,j; sum = 0; memset(count_map,0,sizeof(count_map)); for(i=1;i<=8;i++) { for(j=1;j<=8;j++) { scanf("%lf",&map[i][j]); sum+=map[i][j]; count_map[i][j] = count_map[i][j⑴] + count_map[i⑴][j] - count_map[i⑴][j⑴] + map[i][j]; } } ave = sum*1.0/n; int i2,j2; for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { for(i2=i;i2<=m;i2++) { for(j2 = j;j2<=m;j2++) { s[i][j][i2][j2] = count(i,j,i2,j2); d[0][i][j][i2][j2] = s[i][j][i2][j2]; } } } } } void dp() { int k,i,j,i2,j2; for(k=1;k<n;k++) { for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { for(i2=i;i2<=m;i2++) { for(j2 = j;j2<=m;j2++) { d[k][i][j][i2][j2] = INF; int t; for( t = i;t<i2;t++) d[k][i][j][i2][j2] = min(d[k][i][j][i2][j2], min(d[k⑴][i][j][t][j2] + s[t+1][j][i2][j2], s[i][j][t][j2] + d[k⑴][t+1][j][i2][j2])); for( t = j;t<j2;t++) d[k][i][j][i2][j2] = min(d[k][i][j][i2][j2], min(d[k⑴][i][j][i2][t] + s[i][t+1][i2][j2], s[i][j][i2][t] + d[k⑴][i][t+1][i2][j2])); } } } } } } int main() { while(scanf("%d",&n) != EOF) { init(); dp(); long double ans = d[n⑴][1][1][m][m]*1.0/n - ave*ave; printf("%.3f ",(double)sqrt(ans)); } return 0; }