| ||||||||||
| 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