1191.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#define debug 0
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>
#ifdef debug
	#define NMAX 9
#else 
	#define NMAX 9
#endif
#define INF LONG_MAX
long a[NMAX][NMAX][NMAX][NMAX]={0};
long d[16][NMAX][NMAX][NMAX][NMAX]={0};
int N;
int ans;
solve()
{
	int i,j,m,n;
	for(m=0;m<8;m++)
	{
		for(n=0;n<8;n++)
		{
			for(i=0;i<8;i++)
			{
				for(j=0;j<8;j++)
				{
					if(i+m>=8||j+n>=8)
						continue;
					a[i][j][i+m][j+n]=a[i][j][i][j]+a[i][j+1][i][j+n]+a[i+1][j][i+m][j]+a[i+1][j+1][i+m][j+n];

				}
			}
		}
	}
	long total=a[0][0][7][7];

	for(m=0;m<8;m++)
	{
		for(n=0;n<8;n++)
		{
			for(i=0;i<8;i++)
			{
				for(j=0;j<8;j++)
				{
					a[i][j][m][n]*=a[i][j][m][n];
//					printf("%d",a[i][j][m][n]);
//					printf(" ");
				}
//				printf("\n");
			}
//			printf("\n");
		}
//		printf("\n");
	}

	int k;
	for(m=0;m<8;m++)
	{
		for(n=0;n<8;n++)
		{
			for(i=0;i<8;i++)
			{
				for(j=0;j<8;j++)
				{
					d[0][i][j][m][n]=a[i][j][m][n];
				}
			}
		}
	}
	for(k=1;k<=N-1;k++)
	{
		for(m=0;m<8;m++)
		{
			for(n=0;n<8;n++)
			{
				for(i=0;i<8;i++)
				{
					for(j=0;j<8;j++)
					{
						d[k][i][j][m][n]=INF;
						if(i==m&&j==n)
						{
							d[k][i][j][m][n]=a[i][j][m][n];
							continue;
						}
						if(i>m||j>n)
							continue;
						int t=0;
						for(t=i;t<m;t++)
						{
							if(d[k][i][j][m][n]>d[k-1][i][j][t][n]+a[t+1][j][m][n])
								d[k][i][j][m][n]=d[k-1][i][j][t][n]+a[t+1][j][m][n];
							if(d[k][i][j][m][n]>a[i][j][t][n]+d[k-1][t+1][j][m][n])
								d[k][i][j][m][n]=a[i][j][t][n]+d[k-1][t+1][j][m][n];
						}
						for(t=j;t<n;t++)
						{
							if(d[k][i][j][m][n]>d[k-1][i][j][m][t]+a[i][t+1][m][n])
								d[k][i][j][m][n]=d[k-1][i][j][m][t]+a[i][t+1][m][n];
							if(d[k][i][j][m][n]>a[i][j][m][t]+d[k-1][i][t+1][m][n])
								d[k][i][j][m][n]=a[i][j][m][t]+d[k-1][i][t+1][m][n];
						}
					}
				}
			}
		}
	}
	float tmp1=(float)d[N-1][0][0][7][7]/N;
	float tmp2=(float)total/N;
	tmp2*=tmp2;
	float ans=tmp1-tmp2;
	ans=sqrt(ans);
	printf("%.3f",ans);

	
}
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	scanf("%d",&N);
	int j,i;
	for(i=0;i<8;i++)
	{
		for(j=0;j<8;j++)
		{
			scanf("%d",&a[i][j][i][j]);
		}
	}
	solve();

#if debug
	fclose(stdin);
	fclose(stdout);
#endif;
	return 1;
}