| ||||||||||
| 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 | |||||||||
本题很坑,直接scnaf 不要while(~scnaf),另附题解和数据 dp#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define INF 1000000007
using namespace std;
double sum,ans;
double f[20][10][10][10][10];
int w[10][10],a[10][10];
double he(int x1,int y1,int x2,int y2)
{
double ww;
ww=(w[x2][y2]-w[x1-1][y2]-w[x2][y1-1]+w[x1-1][y1-1]-sum);
return ww*ww;
}
int main()
{
int n,i,j,x1,x2,y1,y2;
scanf("%d",&n);
sum=0;
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
{
scanf("%d",&a[i][j]);
sum+=a[i][j];
}
sum=sum/n;
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
{
w[i][j]=w[i-1][j]+w[i][j-1]-w[i-1][j-1]+a[i][j];
}
for(i=0;i<=n;i++)
for(x1=1;x1<=8;x1++)
for(y1=1;y1<=8;y1++)
for(x2=x1;x2<=8;x2++)
for(y2=y1;y2<=8;y2++)
f[i][x1][y1][x2][y2]=INF;
f[0][1][1][8][8]=0;
for(i=1;i<n;i++)
for(x1=1;x1<=8;x1++)
for(y1=1;y1<=8;y1++)
for(x2=x1;x2<=8;x2++)
for(y2=y1;y2<=8;y2++)
for(j=1;j<=8;j++)
{
if(x1-j>0)
f[i][x1][y1][x2][y2]=min(f[i-1][x1-j][y1][x2][y2]+he(x1-j,y1,x1-1,y2),f[i][x1][y1][x2][y2]);
if(y1-j>0)
f[i][x1][y1][x2][y2]=min(f[i-1][x1][y1-j][x2][y2]+he(x1,y1-j,x2,y1-1),f[i][x1][y1][x2][y2]);
if(x2+j<=8)
f[i][x1][y1][x2][y2]=min(f[i-1][x1][y1][x2+j][y2]+he(x2+1,y1,x2+j,y2),f[i][x1][y1][x2][y2]);
if(y2+j<=8)
f[i][x1][y1][x2][y2]=min(f[i-1][x1][y1][x2][y2+j]+he(x1,y2+1,x2,y2+j),f[i][x1][y1][x2][y2]);
}
ans=INF;
for(x1=1;x1<=8;x1++)
for(y1=1;y1<=8;y1++)
for(x2=x1;x2<=8;x2++)
for(y2=y1;y2<=8;y2++)
{
if(f[n-1][x1][y1][x2][y2]+he(x1,y1,x2,y2)<ans)
ans=f[n-1][x1][y1][x2][y2]+he(x1,y1,x2,y2);
}
ans=ans/n;
ans=sqrt(ans);
printf("%.3f\n",ans);
return 0;
}
数据
input
3
0 1 0 1 0 1 1 0
1 1 0 0 0 1 0 1
1 0 1 0 1 1 0 0
0 1 0 0 0 1 0 1
0 0 0 0 0 0 0 1
1 0 0 1 0 0 0 1
0 1 1 0 1 0 1 1
0 1 0 0 1 1 0 0
output
0.816
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator