poj - 1732 - Phone numbers（dp）

题意：有 N (N <= 50000)个单词（每个单词长度不超过50），问组成长度不超过100的目标串最少要用多少个单词。

题目链接：http://poj.org/problem?id=1732

——>>状态：dp[i] 表示组成前 i 个字符所要用的最少单词数

状态转移方程：dp[i + wLen - 1] = min(dp[i + wLen - 1], dp[i - 1] + 1)

注：单词可以重复使用。。

#include <cstdio>
#include <cstring>
#include <algorithm>const int MAXN = 50000 + 10;
const int MAXW = 50 + 10;
const int MAXT = 100 + 10;
const int INF = 0x3f3f3f3f;
const char *h = "22233344115566070778889990";int N;
char s[MAXT];
char word[MAXN][MAXW], buf[MAXN][MAXW];
int dp[MAXT];
int path[MAXT];
bool first;void Read()
{scanf("%d", &N);for (int i = 0; i < N; ++i){scanf("%s", word[i]);}
}void Init()
{for (int i = 0; i < N; ++i){for (int j = 0; word[i][j] != '\0'; ++j){buf[i][j] = h[word[i][j] - 'a'];}}memset(dp, 0x3f, sizeof(dp));first = true;
}void Dp()
{int len = strlen(s);for (int i = 0; i < len; ++i){for (int j = 0; j < N; ++j){int wLen = strlen(buf[j]);if (i + wLen - 1 < len && strncmp(&s[i], buf[j], wLen) == 0){if (i == 0){dp[i + wLen - 1] = 1;path[i + wLen - 1] = j;}else if (dp[i - 1] + 1 < dp[i + wLen - 1]){dp[i + wLen - 1] = dp[i - 1] + 1;path[i + wLen - 1] = j;}}}}
}void DfsPrint(int pos)
{if (pos == -1) return;DfsPrint(pos - strlen(word[path[pos]]));if (first){first = false;}else{printf(" ");}printf("%s", word[path[pos]]);
}void Output()
{int len = strlen(s);if (dp[len - 1] == INF){puts("No solution.");}else{DfsPrint(len - 1);puts("");}
}int main()
{while (scanf("%s", s) == 1){Read();Init();Dp();Output();}return 0;
}