说来惭愧！自从省选之后自己就没有再碰过程序，最近重新开始。这道非常简单的DP竟然没有看出来！原因应该是没有审清题目……没有注意到“shortest”，直接搜出一组解就输出了……
很简单的DP，不多解释，d[i]=min{d[i],d[i-l[j]]+1}。
另外注意，一个单词可以使用多次。
以下是我的代码：
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
const long maxl=107,maxn=50007,INF=20000007;
const string END_CMD="-1";
const long ff[27]={2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0};
long n,nlen,a[maxl];
long r[maxn][maxl/2],l[maxn];
long d[maxl],f[maxl];
string str[maxn];
bool ok(long ii,long jj)
{
for(long i=ii-l[jj]+1,j=1;i<=ii;i++,j++)
if(a[i]!=r[jj][j])
return false;
return true;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
string tmp;
while(cin>>tmp&&tmp!=END_CMD)
{
nlen=tmp.length();
for(long i=1;i<=nlen;i++) a[i]=(long)(tmp[i-1]-'0');
cin>>n;
for(long i=1;i<=n;i++)
{
cin>>str[i];
l[i]=str[i].length();
for(long j=1;j<=l[i];j++) r[i][j]=ff[str[i][j-1]-'a'];
}
// Input & Init
for(long i=0;i<=nlen;i++) d[i]=INF;
for(long i=0;i<=nlen;i++) f[i]=0;
d[0]=0;
for(long i=1;i<=nlen;i++)
for(long j=1;j<=n;j++)
if(i>=l[j]&&ok(i,j)&&d[i-l[j]]+1<d[i])
{
d[i]=d[i-l[j]]+1;
f[i]=j;
}
if(d[nlen]>=INF)
cout<<"No solution."<<endl;
else
{
long s=0,ans[maxl];
long i=nlen;
while(f[i])
{
s++;ans[s]=f[i];
i-=l[f[i]];
}
for(long i=s;i>=1;i--)
{
if(i<s) cout<<" ";
cout<<str[ans[i]];
}
cout<<endl;
}
}
return 0;
}
代码可能写得有点乱，两个月没写代码了……
posted on 2010-06-15 22:11
lee1r 阅读(352)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划