說來慚愧！自從省選之后自己就沒有再碰過程序，最近重新開始。這道非常簡單的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 閱讀(375)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃