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

本题很坑,直接scnaf 不要while(~scnaf),另附题解和数据 dp

Posted by 409215642 at 2017-01-23 08:52:22 on Problem 1191
#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:
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