2414.txt

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

#include"stdio.h"
#include"string.h"

int best[1024][26];
int min[1024];
char m[1024][1001];
char answer[1001];
int n,l;

bool init()
{
	int i;
	scanf("%d %d",&n,&l);
	if(n==0&&l==0)
		return 0;
	for(i=0;i<n;i++)
		scanf("%s",m[i]);
	return 1;
}

inline int min_int(int a,int b)
{
	return a<b?a:b;
}

void doit(int k)
{
	int i,j;

	for(i=n/2-1;i<n-1;i++)
	for(j=0;j<26;j++)
		best[i][j]=2;


	for(i=0;i<n;i++)
	{
		best[(i+n-2)/2][m[i][k]-'A']--;
		min [(i+n-2)/2]=m[i][k]-'A';
	}
	
	for(i=n/2-2;i>=0;i--)
	{
		min[i]=0;
		for(j=0;j<26;j++)
		{
			best[i][j]=min_int(best[i*2+1][min[i*2+1]]+1,best[i*2+1][j])
					  +min_int(best[i*2+2][min[i*2+2]]+1,best[i*2+2][j]);
			if(best[i][j]<best[i][min[i]])min[i]=j;
		}
	}
}			
int main()
{
	int i,ans;
	while(init())
	{
		ans=0;
		if(n==1)strcpy(answer,m[0]);
		else for(i=0;i<l;i++)
		{
			doit(i);
			ans+=best[0][min[0]];
			answer[i]=min[0]+'A';
		}
		answer[l]='\0';
		printf("%s %d\n",answer,ans);
	}
	return 0;
}