思路,,dp[i][j]表示前j个字母放在前i个键盘上的最小值,,,求dp[i][j]时枚举第i个键盘上放
的字母的个数,,,这里预处理了一个sum[],,表示第j个字母(含j)到最后一个字母的总和,,
思路应该没问题吧,,sample都过了,,哪有那么凑巧的啊,,,,
#include <iostream>
using namespace std;
const int N=100;
__int64 dp[N][N],w[N],sum[N];
char a[N],b[N];
int ans[N][N],res[N];
const __int64 oo=(__int64)1<<61;
int main()
{
	int tt,i,j,k,kk,n,m;
	scanf("%d",&tt);
	for(kk=1;kk<=tt;kk++)
	{
		scanf("%d%d",&n,&m);
		gets(a);gets(a+1);gets(b+1);
		for(i=1;i<=m;i++)
			scanf("%I64d",&w[i]);
		sum[m+1]=0;
		for(i=m;i>=1;i--)
			sum[i]=sum[i+1]+w[i];
		dp[0][0]=0;
		for(i=1;i<=m;i++)
			dp[0][i]=oo;
		for(i=1;i<=n;i++)
			for(j=i;j<=m;j++)
			{
				__int64 tmp=oo,num=w[j];
				for(k=1;k<=j-i+1;k++)
				{
					if(dp[i-1][j-k]+num<tmp)
						tmp=dp[i-1][j-k]+num,ans[i][j]=k;
					num+=sum[j-k]-sum[j+1];
				}
				dp[i][j]=tmp;
			}
		for(i=n,j=m;i>=1;j-=(res[i]=ans[i][j]),i--);
		printf("Keypad #%d:\n",kk);
		for(i=1,k=0;i<=n;i++)
		{
			printf("%c: ",a[i]);
			for(j=1;j<=res[i];j++)
				printf("%c",b[++k]);
			puts("");
		}
		puts("");
	}
	return 0;
}

• 天津人儿？ (139) 20053565 2011-03-11 22:05:53
  • 头次看到这么快回复的,,不是天津的,,不是流行咆哮体么,,,我看看数据,,谢谢,, (187) yy17yy 2011-03-11 22:18:31
  • 我勒个去,,啊,,,膜拜大牛,,A了,,,被我考虑反了,,,加个=号就A了,,, (187) yy17yy 2011-03-11 22:21:36