2531644_wa.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <string.h>
#define INF 1000000000

int a[9][9];
int sum[9][9];
int tot;
int DP[15][9][9][9][9];

int s(int x1,int y1,int x2,int y2)
{
	int tmp;

	tmp = sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];
	return tmp*tmp;
}

int dp(int n,int x1,int y1,int x2,int y2)
{
	int i, j;
	int min = INF, tmp;

	if(n==0)
		return s(x1-1,y1-1,x2,y2);
	if(n>x2-x1+y2-y1)
		return INF;
	for(i = x1; i < x2; i++)
	{
		tmp = s(i,y1-1,x2,y2);
		if(DP[n-1][x1][y1][i][y2]==-1)
			tmp += (DP[n-1][x1][y1][i][y2]=dp(n-1,x1,y1,i,y2));
		else
			tmp += DP[n-1][x1][y1][i][y2];
		if(tmp<min)
			min = tmp;
		tmp = s(x1-1,y1-1,i,y2);
		if(DP[n-1][i+1][y1][x2][y2]==-1)
			tmp += (DP[n-1][i+1][y1][x2][y2]=dp(n-1,i+1,y1,x2,y2));
		else
			tmp += DP[n-1][i+1][y1][x2][y2];
		if(tmp<min)
			min = tmp;
	}
	for(j = y1; j < y2; j++)
	{
		tmp = s(x1-1,j,x2,y2);
		if(DP[n-1][x1][y1][x2][j]==-1)
			tmp += (DP[n-1][x1][y1][x2][j]=dp(n-1,x1,y1,x2,j));
		else
			tmp += DP[n-1][x1][y1][x2][j];
		if(tmp<min)
			min = tmp;
		tmp = s(x1-1,y1-1,x2,j);
		if(DP[n-1][x1][j+1][x2][y2]==-1)
			tmp += (DP[n-1][x1][j+1][x2][y2]=dp(n-1,x1,j+1,x2,y2));
		else
			tmp += DP[n-1][x1][j+1][x2][y2];
		if(tmp<min)
			tmp = min;
	}
	return min;
}

int main()
{
	int i, j, n;
	int ans;

	scanf("%d",&n);
	tot = 0;
	memset(DP,-1,sizeof(DP));
	for(i = 1; i <= 8; i++)
		for(j = 1; j <= 8; j++)
			scanf("%d",&a[i][j]),tot+=a[i][j];
	tot *= tot;
	for(i = 0; i <= 8; i++)
		sum[i][0] = sum[0][i] = 0;
	for(i = 1; i <= 8; i++)
		for(j = 1; j <= 8; j++)
			sum[i][j] = sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
	ans = dp(n-1,1,1,8,8);
	printf("%.3lf\n",sqrt(ans*1.0/n-tot*1.0/(n*n)));
	return 0;
}