分类里属于DP。分别用DP和搜索两种方法进行了求解。一开始想的就是搜索，加了一个求剩余块均方差的剪枝就AC了，110MS。后面的DP就没有任何优化，直接是整个5维数组全算一遍的，但也0MS了。
搜索：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<cstdio> #include<cstring> #include<cmath> int n,a[9][9],b[9][9]; double md; double mnmsd; void dfs(int d,int xl,int yb,int xr,int yt,double e,double r) { int i,j,k,l; double f; if(d==n-1) { f=b[xr][yt]-b[xr][yb-1]-b[xl-1][yt]+b[xl-1][yb-1]; e+=pow(f-md,2); double msd=sqrt(e/n); mnmsd=msd<mnmsd?msd:mnmsd; return; } if(sqrt((e+pow(r/(n-d)-md,2))/n)>=mnmsd) return; for(i=xl;i<xr;i++) { f=b[i][yt]-b[xl-1][yt]-b[i][yb-1]+b[xl-1][yb-1]; dfs(d+1,i+1,yb,xr,yt,e+pow(f-md,2),r-f); f=b[xr][yt]-b[i][yt]-b[xr][yb-1]+b[i][yb-1]; dfs(d+1,xl,yb,i,yt,e+pow(f-md,2),r-f); } for(j=yb;j<yt;j++) { f=b[xr][j]-b[xl-1][j]-b[xr][yb-1]+b[xl-1][yb-1]; dfs(d+1,xl,j+1,xr,yt,e+pow(f-md,2),r-f); f=b[xr][yt]-b[xl-1][yt]-b[xr][j]+b[xl-1][j]; dfs(d+1,xl,yb,xr,j,e+pow(f-md,2),r-f); } } int main() { int i,j,k,l; while(~scanf("%d",&n)) { mnmsd=1e30; md=0; memset(b,0,sizeof b); k=0; for(i=1;i<=8;i++) { for(j=1;j<=8;j++) { scanf("%d",&a[i][j]); md+=a[i][j]; k+=a[i][j]; b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]; } } md/=n; dfs(0,1,1,8,8,0,k); printf("%.3f\n",mnmsd); } return 0; } |
DP：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<cstdio> #include<cstring> #include<cmath> int n,a[9][9],b[9][9]; double md,dp[9][9][9][9][16]; double calc(int xl,int yb,int xr,int yt,int c) { if(c==1) return pow(b[xr][yt]-b[xl-1][yt]-b[xr][yb-1]+b[xl-1][yb-1]-md,2); int i; double e=1e30,f; for(i=xl;i<xr;i++) { f=dp[xl][yb][i][yt][1]+dp[i+1][yb][xr][yt][c-1]*(c-1); e=f<e?f:e; f=dp[xl][yb][i][yt][c-1]*(c-1)+dp[i+1][yb][xr][yt][1]; e=f<e?f:e; } for(i=yb;i<yt;i++) { f=dp[xl][yb][xr][i][1]+dp[xl][i+1][xr][yt][c-1]*(c-1); e=f<e?f:e; f=dp[xl][yb][xr][i][c-1]*(c-1)+dp[xl][i+1][xr][yt][1]; e=f<e?f:e; } return e/c; } int main() { int h,i,j,k,l; double e,f; while(~scanf("%d",&n)) { memset(b,0,sizeof b); memset(dp,127,sizeof dp); md=0; for(i=1;i<9;i++) for(j=1;j<9;j++) { scanf("%d",&a[i][j]); b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j]; md+=a[i][j]; } md/=n; for(h=0;h<8;h++) for(i=0;i<8;i++) for(j=1;j+h<9;j++) for(k=1;k+i<9;k++) for(l=1;l<=n;l++) dp[j][k][j+h][k+i][l]=calc(j,k,j+h,k+i,l); printf("%.3f\n",sqrt(dp[1][1][8][8][n])); } return 0; } |