Ring

题目大意：斯蒂文想送给他女盆友一个戒指，并且他想在戒指上刻一些字，他非常了解他女盆友喜欢什么单词，比如"love""forvevr"....并且他还把女盆友喜欢的单词弄了一个高兴度，他现在准备在这个戒指上刻上一个长度不超过N的句子，并且这个句子的高兴度是最大的，如果有多个这样的句子，选择最短的，如果还有多个选择字典序最小的。

 

分析：比较容易想到DP来做，定义数组dp[Ni][kNode]，保存第i长度到达k节点的最大价值，然后再用一个数组来保存路径就行了，注意dp数组初始化的时候应该初始化成一个很小的值...在这wa了好多次......................

 

代码如下：

======================================================================================================================================

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

const int MAXN = 1207;
const int MAXM = 57;
const int MaxSon = 26;
const int oo = 1e9+7;

int dp[MAXM][MAXN];
char path[MAXM][MAXN][MAXM];

struct Ac_Trie
{
    int next[MAXN][MaxSon];
    int Fail[MAXN], End[MAXN];
    int cnt, root;

    int newnode()
    {
        for(int i=0; i<MaxSon; i++)
            next[cnt][i] = -1;
        Fail[cnt] = End[cnt] = false;

        return cnt++;
    }
    void InIt()
    {
        cnt = 0;
        root = newnode();
    }

    void Insert(char s[], int val)
    {
        int now = root;

        for(int i=0; s[i]; i++)
        {
            int k = s[i]-'a';

            if(next[now][k] == -1)
                next[now][k] = newnode();
            now = next[now][k];
        }

        End[now] = val;
    }
    void GetFial()
    {
        queue<int>Q;
        int now = root;

        for(int i=0; i<MaxSon; i++)
        {
            if(next[now][i] == -1)
                next[now][i] = root;
            else
            {
                Fail[next[now][i]] = root;
                Q.push(next[now][i]);
            }
        }

        while(Q.size())
        {
            now = Q.front();
            Q.pop();

            for(int i=0; i<MaxSon; i++)
            {
                if(next[now][i] == -1)
                    next[now][i] = next[Fail[now]][i];
                else
                {
                    Fail[next[now][i]] = next[Fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }
};
Ac_Trie ac;

bool cmp(char a[], char b[])
{
    int len_a = strlen(a);
    int len_b = strlen(b);

    if(len_a != len_b)
        return len_a > len_b;
    return strcmp(a, b) > 0;
}

int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        int i, j, k, N, M, val;
        char s[107][17];
        ac.InIt();

        scanf("%d%d", &N, &M);

        for(i=0; i<M; i++)
            scanf("%s", s[i]);

        for(i=0; i<M; i++)
        {
            scanf("%d", &val);
            ac.Insert(s[i], val);
        }

        ac.GetFial();

        for(i=0; i<=N; i++)
        for(j=0; j<ac.cnt; j++)
            dp[i][j] = -oo;

        memset(path, false, sizeof(path));

        char ans[MAXM] = {0};
        int Max = 0;
        dp[0][0] = 0;

        for(i=0; i<N; i++)
        for(j=0; j<ac.cnt; j++)
        {
            char temp[57] = {0};
            strcpy(temp, path[i][j]);
            int len = strlen(temp);

            for(k=0; k<MaxSon; k++)
            {
                int next = ac.next[j][k];
                temp[len] = k+'a';

                val = dp[i][j]+ac.End[next];

                if(dp[i+1][next] < val || (dp[i+1][next]==val && cmp(path[i+1][next], temp) ) )
                {
                    dp[i+1][next] = val;
                    strcpy(path[i+1][next], temp);

                    if(Max < val || (Max==val && cmp(ans, temp)))
                    {
                        Max = val;
                        strcpy(ans, temp);
                    }
                }
            }
        }
        printf("%s
", ans);
    }

    return 0;
}