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