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 |
求大神帮忙看,前面dp部分不用看肯定对,下面计算哪里出错了?谢谢~#include<cmath> #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,sum; double x; int val[10][10],qzh[10][10],f[10][10][10][10][15]; int gpow(int x){ return x*x; } int calc(int x1,int y1,int x2,int y2){ return qzh[x2][y2]-qzh[x2][y1-1]-qzh[x1-1][y2]+qzh[x1-1][y1-1]; } int main(){ scanf("%d",&n); for(int i=1;i<=8;i++){ for(int j=1;j<=8;j++){ scanf("%d",&val[i][j]); sum+=val[i][j]; qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+val[i][j]; } } x=(double)sum/64; memset(f,0x3f,sizeof f); for(int x1=1;x1<=8;x1++){ for(int y1=1;y1<=8;y1++){ for(int x2=x1;x2<=8;x2++){ for(int y2=y1;y2<=8;y2++) f[x1][y1][x2][y2][0]=gpow(qzh[x2][y2]-qzh[x1-1][y2]-qzh[x2][y1-1]+qzh[x1-1][y1-1]); } } } for(int k=1;k<n;k++){ for(int x1=1;x1<=8;x1++){ for(int y1=1;y1<=8;y1++){ for(int x2=x1;x2<=8;x2++){ for(int y2=y1;y2<=8;y2++){ for(int p=x1;p<x2;p++) f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],min(f[x1][y1][p][y2][k-1]+gpow(calc(p+1,y1,x2,y2)),f[p+1][y1][x2][y2][k-1]+gpow(calc(x1,y1,p,y2)))); for(int p=y1;p<y2;p++) f[x1][y1][x2][y2][k]=min(f[x1][y1][x2][y2][k],min(f[x1][y1][x2][p][k-1]+gpow(calc(x1,p+1,x2,y2)),f[x1][p+1][x2][y2][k-1]+gpow(calc(x1,y1,x2,p)))); } } } } } double ans=f[1][1][8][8][n-1]; ans+=(double)gpow(x)*n; ans-=sum*2*x; ans/=n; printf("%.3lf",sqrt((double)ans)); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator