URAL_1002
dp的思路还是比较好想的，可以用f[i]表示递推到第i个数字的时候最短用几个单词表示。这样只要枚举当前单词的起始位置j，如果j~i可以构成一个单词，那么就尝试更新f[i]，而判断j~i是否可以构成一个单词的过程可以用哈希表实现。
#include<stdio.h> #include<string.h> #define INF 0x3f3f3f3f #define HASH 1000003 #define MAXD 50010 #define MAXL 60 #define MAXN 110 int N, head[HASH], next[MAXD], f[MAXN], p[MAXN], g[MAXN], len[MAXD]; char b[MAXN], ch[300], word[MAXD][MAXL], code[MAXD][MAXL]; int hash(char *str, int a, int b) { int i, h = 0, seed = 131; for(i = a; i <= b; i ++) h = h * seed + str[i]; return (h & 0x7fffffff) % HASH; } void Insert(int s) { int h = hash(code[s], 0, len[s] - 1); next[s] = head[h]; head[h] = s; } void init() { int i, j; memset(head, -1, sizeof(head)); ch['o'] = ch['q'] = ch['z'] = '0'; ch['i'] = ch['j'] = '1'; ch['a'] = ch['b'] = ch['c'] = '2'; ch['d'] = ch['e'] = ch['f'] = '3'; ch['g'] = ch['h'] = '4'; ch['k'] = ch['l'] = '5'; ch['m'] = ch['n'] = '6'; ch['p'] = ch['r'] = ch['s'] = '7'; ch['t'] = ch['u'] = ch['v'] = '8'; ch['w'] = ch['x'] = ch['y'] = '9'; scanf("%d", &N); for(i = 0; i < N; i ++) { scanf("%s", word[i]); for(j = 0; word[i][j]; j ++) code[i][j] = ch[word[i][j]]; len[i] = j; Insert(i); } } int isequal(int x, int s) { int i; for(i = 0; i < len[s]; i ++) if(b[x + i] != code[s][i]) return 0; return 1; } void dp(int x, int y) { int i, h = hash(b, x, y); for(i = head[h]; i != -1; i = next[i]) if(len[i] == y - x + 1 && isequal(x, i)) break; if(i != -1 && f[x - 1] + 1 < f[y]) { f[y] = f[x - 1] + 1; p[y] = x - 1, g[y] = i; } } void print(int cur) { if(p[cur] == 0) { printf("%s", word[g[cur]]); return ; } print(p[cur]); printf(" %s", word[g[cur]]); } void solve() { int i, j, k; memset(f, 0x3f, sizeof(f)); f[0] = 0; for(i = 1; b[i]; i ++) for(j = 1; j <= i; j ++) dp(j, i); -- i; if(f[i] == INF) printf("No solution.\n"); else { print(i); printf("\n"); } } int main() { for(;;) { scanf("%s", b + 1); if(b[1] == '-') break; init(); solve(); } return 0; }