Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
参考代码#include<iostream> #include<cmath> using namespace std; double f[15][9][9][9][9],sum[9][9]; int x,n; double cal(int x1,int y1,int x2,int y2) { double ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; return ans*ans; } double dfs(int k,int x1,int y1,int x2,int y2) { int i,j; double min1=0x3fffffff; if(k==1)return cal(x1,y1,x2,y2); if(fabs(f[k][x1][y1][x2][y2])>1e-6)return f[k][x1][y1][x2][y2]; for(i=x1;i<x2;i++) min1=min(min1,min(dfs(k-1,i+1,y1,x2,y2)+cal(x1,y1,i,y2),dfs(k-1,x1,y1,i,y2)+cal(i+1,y1,x2,y2))); for(j=y1;j<y2;j++) min1=min(min1,min(dfs(k-1,x1,y1,x2,j)+cal(x1,j+1,x2,y2),dfs(k-1,x1,j+1,x2,y2)+cal(x1,y1,x2,j))); f[k][x1][y1][x2][y2]=min1; return min1; } int main() { int i,j; scanf("%d",&n); for(i=1;i<=8;i++) for(j=1;j<=8;j++) { scanf("%d",&x); sum[i][j]=x+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; } printf("%.3lf\n",sqrt(dfs(n,1,1,8,8)/n-pow(sum[8][8]/n,2))); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator