> #include <iostream>
> #include <stdio.h>
> #include <cmath>
> using namespace std;
> 
> #define min(x,y) x<y?x:y
> #define M 8
> 
> int d[15][M+1][M+1][M+1][M+1] = {0};
> int s[M+1][M+1] = {0};
> int c[M+1][M+1] = {0};
> int n;
> 
> void pre()
> {
> 	int i,j;
> 	for(i = 0;i <= M;i++)
> 		s[i][0] = 0;
> 	for(j = 0;j <= M;j++)
> 		s[0][j] = 0;
> 	for(i = 1;i <= M;i++)
> 		for(j = 1;j <= M;j++)
> 			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + c[i][j];
> }
> int f(int i_min,int j_min,int i_max,int j_max)
> {
> 	int temp = s[i_max][j_max] - s[i_min-1][j_max] -s[i_max][j_min-1] +s[i_min-1][j_min-1];
> 	return temp*temp;
> }
> int main()
> {
> 	int i,j,k,a,b,temp;
> 	int x1,y1,x2,y2,min_a,min_b;
> 	int sum = 0;
> 	double x,ans;
> 	scanf("%d",&n);
> 	for(i = 1;i <= M;i++)
> 	{
> 		for(j = 1;j <= M;j++)
> 		{
> 			scanf("%d",&c[i][j]);
> 			sum += c[i][j];
> 		}
> 	}
> 	x = (double)sum/n;
> 	
> 	pre();
> 	
> 	for(x1 = 1;x1 <= M;x1++)
> 	{
> 		for(y1 = 1;y1 <= M;y1++)
> 		{
> 			for(x2 = 1;x2 <= M;x2++)
> 			{
> 				for(y2 = 1;y2 <= M;y2++)
> 				{
> 					
> 					d[0][x1][y1][x2][y2] = f(x1,y1,x2,y2);
> 				}
> 			}
> 		}
> 	}
> 	
> 	for(k = 1;k < n;k++)
> 	{
> 		for(x1 = 1;x1 <= M;x1++)
> 		{
> 			for(y1 = 1;y1 <= M;y1++)
> 			{
> 				for(x2 = 1;x2 <= M;x2++)
> 				{
> 					for(y2 = 1;y2 <= M;y2++)
> 					{
> 						min_a = INT_MAX;
> 						for(a = x1;a < x2;a++)
> 						{
> 							temp = min(d[k-1][x1][y1][a][y2]+d[0][a+1][y1][x2][y2],d[k-1][a+1][y1][x2][y2]+d[0][x1][y1][a][y2]);
> 							if(min_a > temp)
> 								min_a = temp;
> 						}
> 						
> 						min_b = INT_MAX;
> 						for(b = y1;b < y2;b++)
> 						{
> 							temp = min(d[k-1][x1][y1][x2][b]+d[0][x1][b+1][x2][y2],d[k-1][x1][b+1][x2][y2]+d[0][x1][y1][x2][b]);
> 							if(min_b > temp)
> 								min_b = temp;
> 						}
> 						
> 						d[k][x1][y1][x2][y2] = min(min_a,min_b);
> 					}
> 				}
> 			}
> 		}
> 	}
> 	ans = (double)d[n-1][1][1][8][8]/n - x*x;
> 	ans = sqrt(ans);
> 	printf("%.3f\n",ans);
> 	return 0;
> }

• Re:啊啊啊啊，为什么我的总是WA，哪位大侠给看下…… (17) zgsxzdl 2010-07-21 21:37:31