Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求大神帮忙看,前面dp部分不用看肯定对,下面计算哪里出错了?谢谢~

Posted by YoungNeal at 2018-02-22 21:12:56 on Problem 1191
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator