动归的题目，话说不知道为什么做的时候2了一下，用记忆化做的都没看出来是动归。。估计下意识的觉得递归输出方便吧
have[i][j]表示从i到j最少需要多少个单词，不能得到则为-1。f[i][j]预处理i到j能否由一个单词得到，能的话则为那个单词的位置值。
剩下的就是茫茫的递归了。。
#include<stdio.h>
#include<string.h>
int have[201][201];
int f[201][201];
char ss[201];
char s[50001][101];
char c[28]="022233344115566070778889990";
long l[50001];
long n,i,ll,j,k,first;
void pri(long l,long r)
{
long i;
if (f[l][r]!=0)
{
if (first!=0)
printf(" ");
first=1;
printf("%s",s[f[l][r]]);
return;
}
for (i=l;i<r;i++)
if (have[l][i]!=-1 && have[i+1][r]!=-1)
if (have[l][i]+have[i+1][r]==have[l][r])
{
pri(l,i);
pri(i+1,r);
return;
}
}
int write(long l,long r)
{
long i;
if (have[l][r]!=20000000)
return have[l][r];
if (f[l][r]!=0)
{
have[l][r]=1;
return 1;
}
if (l==r)
{
have[l][r]=-1;
return -1;
}
for (i=l;i<r;i++)
if (write(l,i)!=-1 && write(i+1,r)!=-1)
{
if (have[l][r]>have[l][i]+have[i+1][r])
have[l][r]=have[l][i]+have[i+1][r];
}
if (have[l][r]==20000000)
have[l][r]=-1;
return have[l][r];
}
int main()
{
first=-1;
while (2>1)
{
memset(ss,0,sizeof(ss));
scanf("%s",ss);
if (ss[0]<48 || ss[0]>57)
return 0;
if (first!=-1)
printf("\n");
first=0;
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%s",s[i]);
l[i]=strlen(s[i]);
}
memset(f,0,sizeof(f));
ll=strlen(ss);
for (i=0;i<ll;i++)
for (j=1;j<=n;j++)
{
if (ss[i]==c[s[j][0]-96])
{
k=1;
while (k<l[j] && ss[i+k]==c[s[j][k]-96])
{
k++;
}
if (k==l[j])
f[i][i+k-1]=j;
}
}
for (i=0;i<=ll-1;i++)
for (j=0;j<=ll-1;j++)
have[i][j]=20000000;
i=write(0,ll-1);//处理出所有值
if (i!=-1)
{
pri(0,ll-1);//递归输出最优解
}
else
printf("No solution.");
}
}
posted on 2011-06-27 16:31
梦转千寻 阅读(62)
评论(0) 编辑 收藏 引用