2532264_ac_0ms_548k.cpp

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

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

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

 void  init()
  {
     int  x1, y1, x2, y2;
     int  i, j;
     int  sum;
     for  (x1 = 1 ; x1 <= 8 ; x1 ++ )
         for  (y1 = 1 ; y1 <= 8 ; y1 ++ )
             for  (x2 = x1; x2 <= 8 ; x2 ++ )
                 for  (y2 = y1; y2 <= 8 ; y2 ++ )
                  {
                    sum  =   0 ;
                     for  (i = x1; i <= x2; i ++ )
                         for  (j = y1; j <= y2; j ++ )
                            sum  +=  a[i][j];
                    s[x1][y1][x2][y2]  =  sum;
                } 
} 
int S(int x1,int y1,int x2,int y2)
{
	return s[x1][y1][x2][y2]*s[x1][y1][x2][y2];
}

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,y1,x2,y2);
	for(i = x1; i < x2; i++)
	{
		if(DP[n-1][x1][y1][i][y2]<INF)
		{
		tmp = S(i+1,y1,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;}
		if(DP[n-1][i+1][y1][x2][y2]<INF)
		{
			tmp = S(x1,y1,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++)
	{
		if(DP[n-1][x1][y1][x2][j]<INF)
		{
		tmp = S(x1,j+1,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;}
		if(DP[n-1][x1][j+1][x2][y2]<INF)
		{
		tmp = S(x1,y1,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)
			min = tmp;}
	}
	DP[n][x1][y1][x2][y2] = min;
	return min;
}

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

	//freopen("data.txt","r",stdin);
	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];
	init();
	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("%d\n",ans);
	printf("%.3lf\n",sqrt(ans*1.0/n-tot*1.0/(n*n)));
	return 0;
}