English Game【字典树+dp】

素颜马尾好姑娘i 2022-05-26 06:50 30阅读 0赞

## English Game ##

#### 题目描述 ####

This English game is a simple English words connection game.  
The rules are as follows: there are N English words in a dictionary, and every word has its own weight v. There is a weight if the corresponding word is used. Now there is a target string X. You have to pick some words in the dictionary, and then connect them to form X. At the same time, the sum weight of the words you picked must be the biggest.

#### 输入 ####

There are several test cases. For each test, N (1<=n<=1000) and X (the length of x is not bigger than 10000) are given at first. Then N rows follow. Each row contains a word wi (the length is not bigger than 30) and the weight of it. Every word is composed of lowercases. No two words in the dictionary are the same.

#### 输出 ####

For each test case, output the biggest sum weight, if you could not form the string X, output -1.

#### 样例输入 ####

1 aaaa  
a 2  
3 aaa  
a 2  
aa 5  
aaa 6  
4 abc  
a 1  
bc 2  
ab 4  
c 1  
3 abcd  
ab 10  
bc 20  
cd 30  
3 abcd  
cd 100  
abc 1000  
bcd 10000

#### 样例输出 ####

8  
7  
5  
40  
\-1

#### 题意概括： ####

给出n个词，每个词有一个权值，组成一个词典，求给出的那个字符串最大的权值和。

#### 解题思路： ####

先给词典建一个字典树（trie），然后对给出的字符串用动态规划求出最大权值和。

#### AC代码： ####

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    
    #define N 100010
    
    int f[N][30];
    
    int main()
    {
        int i, j, k, n, m, cnt;
        int dp[N], g[N];
        char s[N], str[N];
        while(~scanf("%d%s", &n, s+1)){
            memset(f[0], 0, sizeof(f[0]));
            cnt = 0;
            while(n--){
                scanf("%s%d", str, &m);
                k = 0;
                for(i = 0; str[i]; i++){
                    if(!f[k][str[i]-'a']){
                        f[k][str[i]-'a'] = ++cnt;
                        memset(f[cnt], 0, sizeof(f[cnt]));
                        g[cnt] = 0;
                    }
                    k = f[k][str[i]-'a'];
                }
                g[k] = max(g[k], m);
            }
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for(i = 1; s[i]; i++){
                if(!dp[i-1]) continue;
                k = 0;
                for(j = i; s[j]; j++){
                    if(f[k][s[j]-'a']){
                        k = f[k][s[j]-'a'];
                        if(g[k]) dp[j] = max(dp[j], dp[i-1]+g[k]);
                    }
                    else break;
                }
            }
            printf("%d\n", dp[strlen(s+1)]-1);
        }
        return 0;
    }