pku(1191) 棋盘分割

作者在 2008-08-22 12:32:59 发布以下内容
黑书 p116页上有详细的分析
 
代码
如下:
#include <iostream>
#include <math.h>
using namespace std;
int grid[8][8];
int d[16][9][9][9][9];
int sm[9][9];
int const INF=10000000;
int n;
int sum(int i,int j,int s,int t)
{
	return sm[s][t]-sm[i][t]-sm[s][j]+sm[i][j];
}
int comp(int a,int b,int c)
{
	if(a<=b&&a<=c)
		return a;
	else if(b<=c)
		return b;
	else
		return c;
}
int minn(int k,int i,int j,int s,int t)
{
	int r;
	int tem1,tem2;
	int min=INF;
	for( r=i;r<s;r++)
	{
		tem1=d[k][i][j][r][t]+sum(r,j,s,t)*sum(r,j,s,t);
		tem2=d[k][r][j][s][t]+sum(i,j,r,t)*sum(i,j,r,t);
		min=comp(min,tem1,tem2);
	}
	for( r=j;r<t;r++)
	{
		tem1=d[k][i][j][s][r]+sum(i,r,s,t)*sum(i,r,s,t);
		tem2=d[k][i][r][s][t]+sum(i,j,s,r)*sum(i,j,s,r);
		min=comp(min,tem1,tem2);
	}
	return min;
}
void input()
{
	int i,j,k,s,t;
	memset(grid,0,sizeof(grid));
	for(k=0;k<=15;k++)
	for(i=0;i<=8;i++)
		for(j=0;j<=8;j++)
			for(s=0;s<=8;s++)
				for(t=0;t<=8;t++)
					d[k][i][j][s][t]=INF;
	cin >>n;
	for(i=0;i<8;i++)
		for(j=0;j<8;j++)
			cin >>grid[i][j];
}
void init()
{
	int i,j,s,t;
	for(i=0;i<=8;i++)
	{
		sm[0][i]=0;
		sm[i][0]=0;
	}
	for(i=1;i<=8;i++)
	{
		int temp=0;
		for(j=1;j<=8;j++)
		{
			temp+=grid[i-1][j-1];
			sm[i][j]=sm[i-1][j]+temp;
		}
	}
	for(i=0;i<=8;i++)
		for(j=0;j<=8;j++)
			for(s=i+1;s<=8;s++)
				for(t=j+1;t<=8;t++)
				{
					int  tt=sum(i,j,s,t);
					d[0][i][j][s][t]=tt*tt;
				}
	return ;

}
void dp()
{
	int i,j,k,s,t;
	for(k=1;k<n;k++)
	{
		for(i=0;i<=8;i++)
			for(j=0;j<=8;j++)
				for(s=i+1;s<=8;s++)
					for(t=j+1;t<=8;t++)
					{
						d[k][i][j][s][t]=minn(k-1,i,j,s,t);
					}
	}
}
int main()
{
	input();
	init();
	dp();
	printf("%.3lf\n",sqrt(d[n-1][0][0][8][8]*1.0/double(n)-sm[8][8]*sm[8][8]*1.0/double(n*n)));
	return 0;
}
acm | 阅读 4848 次
文章评论,共0条
游客请输入验证码
浏览260764次