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