poj1732

题目大意：给你一个a..z与数字的对应表及一些单词

再给你一个目标串数字串。。问你最少用那些单词可以拼成数字串。。

思路：dp

f[i]表示前i个最少用几个单词拼成

f[i]= f[i - len[k]] + 1 (第k个单词对应数字正好相符)

 1 /*
 2   State:Accepted
 3   Time:2013-03-10 14:35:57
 4 */
 5 #include <cstring>
 6 #include <string>
 7 #include <fstream>
 8 #include <cstdlib>
 9 #include <cstdio>
10 using namespace std;
11 char s[150],s1[50001][55];
12 const int num[26]={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};
13 int m , a[50010][55] , f[200] , fpt[200],n;
14 void init(){
15     scanf("%s",&s);
16     n = strlen(s); 
17     scanf("%d",&m);
18     for (int i = 1; i <= m; ++i){
19           scanf("%s",&s1[i]);
20           a[i][0] = strlen(s1[i]);
21           for (int j = 0; j < strlen(s1[i]); ++j)
22              a[i][j + 1] = num[s1[i][j] - 'a'];
23     }
24 }
25 
26 void print(int now){
27      if (now <= 0) return;
28      int len = a[fpt[now]][0];
29      print(now - len);
30     // printf("ID=%d J=%d :",now , fpt[now]);
31      printf("%s ",s1[fpt[now]]); 
32 }
33 
34 void dp(){
35      bool bo;
36      int now;
37      for (int i = 0; i <= n; ++i)  
38          f[i] = 0xffffff;
39      f[0] = 0;
40      for  (int i = 0; i < n; ++i)
41           for (int j = 1; j <= m; ++j)
42            {
43               bo = true;
44               for (int l = 1 ; l <= a[j][0]; ++l)
45                  if  (i + l > n || a[j][l] != num[ s[i + l] - 'a'])
46                    {
47                       bo = false;
48                       break;
49                    };
50               now = i + a[j][0];
51               if (bo && f[i] + 1 < f[now]){
52                        f[now] =  f[i] + 1;
53                        fpt[now] = j;
54               }
55             }
56      print(n);
57      printf("\n");
58 }
59 
60 int main(){
61     freopen("poj1732.in","r",stdin);
62     freopen("poj1732.out","w",stdout);
63     init();
64     dp();
65 }