1404.txt

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

#include <stdio.h>

int K,L;
char key[100];
char letter[100];
int F[100];
int p[100];
int best;
int map[100][100][100];
int father[100][100];
int q[100];

int main()
{
	int t,c;
	int i,j,m,n;
	int limitA,limitB;
	char str[100];
	scanf("%d",&t);
	c=0;
	while(c<t)
	{
		c++;
		scanf("%d %d",&K,&L);
		scanf("%s",str);
		for(i=1;i<=K;i++)key[i]=str[i-1];
		scanf("%s",str);
		for(i=1;i<=L;i++)letter[i]=str[i-1];
		for(i=1;i<=L;i++)scanf("%d",&F[i]);
		for(i=1;i<=K;i++)
		{
			for(j=1;j<=L;j++)
			{
				for(m=1;m<=j;m++)
				{
					map[i][j][m]=-1;
				}
			}
		}
		limitA=L-K+1;
		map[1][1][1]=F[1];
		for(i=2;i<=L;i++)
		{
			for(j=2;j<=i && j<=K;j++)
			{
				limitB=i-j+1;
				for(m=1;m<=limitA && m<=limitB;m++)
				{
					if(map[j-1][i-1][m]>=0)
					{
						if(map[j][i][1]<0 || map[j][i][1]>=map[j-1][i-1][m]+F[i])
						{
							map[j][i][1]=map[j-1][i-1][m]+F[i];
							father[j][i]=m;
						}
					}
				}
			}
			for(j=1;j<=i && j<=K;j++)
			{
				limitB=i-j+1;
				for(m=2;m<=limitA && m<=limitB;m++)
				{
					if(map[j][i-1][m-1]>=0)
					{
						map[j][i][m]=m*F[i]+map[j][i-1][m-1];
					}

				}
			}
		}
		best=1000000000;
		for(i=1;i<=L;i++)
		{
			if(map[K][L][i]>=0 && map[K][L][i]<=best)
			{
				j=K,m=L,n=i;
				while(m>=1)
				{
					q[j]=1;
					while(n>1)
					{
						n--,m--;
						q[j]++;
					}
					n=father[j][m];
					m--;
					j--;
				}
				best=map[K][L][i];
				for(j=1;j<=K;j++)p[j]=q[j];
			}
		}
		m=0;
		printf("Keypad #%d:\n",c);
		for(i=1;i<=K;i++)
		{
			printf("%c: ",key[i]);
			n=p[i];
			while(n-->0)
			{
				m++;
				printf("%c",letter[m]);
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}