学步园

题意：有 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;
}