ACM模版

描述


题解

一看这个题，我第一感觉就是 dp，想着可能是 map + 区间 dp，但是发现数据太大，开不来二维 dp，有些手足无措，真情太少，套路太深，后来搞懂原来这个是字典树 + dp，但是不是简单的区间 dp，具体我也不知道这叫啥 dp，反正挺有趣的一个 dp，具体代码里很容易看懂，就是不容易想……

这个题用 map + dp 应该是可解的，不过涉及到字符串切割的问题稍微麻烦一些，也可能效率没有直接字典树搞来的快，毕竟我们需要不断用子串去匹配。

哎，dp 博大精深，需要好好学习啦，几个月前刷过 dp 专题，现在已经忘却了太多，智商不够用了，忘性太大了~~~

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN = 3e5 + 10;
const int MAX_WORD_LEN = 30;

int flag[MAXN];
char s[MAXN];
int Trie[MAXN][26], sz;
double dp[MAXN];
double val[MAXN];

void format(int x)
{
    if (!x)
    {
        return ;
    }

    format(flag[x]);

    if (flag[x])
    {
        printf(" ");
    }
    for (int i = flag[x] + 1; i <= x; i++)
    {
        printf("%c", s[i]);
    }
}

int main()
{
    int N, T;
    while (cin >> N)
    {
        sz = 0;
        val[0] = 0;
        memset(Trie[0], 0, sizeof(Trie[0]));

        for (int i = 0; i < N; i++)
        {
            scanf("%s", s);
            int k = 0;
            int len = (int)strlen(s);
            for (int j = 0; j < len; j++)
            {
                int x = s[j] - (s[j] >= 'a' ? 'a' : 'A');
                if (!Trie[k][x])
                {
                    Trie[k][x] = ++sz;
                    memset(Trie[sz], 0, sizeof(Trie[sz]));
                    val[sz] = 0;
                }
                k = Trie[k][x];
            }
            scanf("%lf", &val[k]);
            val[k] = log(val[k]) * len * len;
        }

        cin >> T;
        for (int i = 0; i < T; i++)
        {
            scanf("%s", s + 1);
            memset(dp, 0, sizeof(dp));
            int len = (int)strlen(s + 1);
            for (int j = 1; j <= len; j++)
            {
                int rt = 0;
                for (int k = 0; k < MAX_WORD_LEN; k++)
                {
                    if (j + k > len)
                    {
                        break;
                    }
                    int x = s[j + k] - (s[j + k] >= 'a' ? 'a' : 'A');
                    if (Trie[rt][x])
                    {
                        rt = Trie[rt][x];
                        if (dp[j + k] < dp[j - 1] + val[rt])
                        {
                            dp[j + k] = dp[j - 1] + val[rt];
                            flag[j + k] = j - 1;
                        }
                    }
                    else
                    {
                        break;
                    }
                }
            }

            printf("%lf\n", dp[len]);
            format(len);
            puts("");
        }
    }

    return 0;
}