传送门：点击打开链接
题意：告诉你一个字典，每个单词有一个权值，再给你一个字符串，问这个字符串用字典中的单词不重复字母的覆盖，最大权值是多少。一个单词可以重复出现
思路：先如果不考虑单词匹配，那么就是一个单纯的dp,dp[i]表示前i个已被完全覆盖此时的权值大小，如果在i位置后面有一个单词的长度为l，权值是w，且此时在i位置后长度为l的子字符串就等于那个单词，说明那个单词能放在这个位置，就有dp[l+i]=max(dp[l+i],dp[i]+w)
所以，问题转换为，如何找对应的位置有哪些单词可以匹配
我们很容易想到利用字典树去维护，因为是从左往右匹配的，这样就存在大量的剪枝
trie写的比较搓，不要轻易模仿..等写的不搓后再改一份..
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;char S[MX];
int dp[MX];struct Node {int num;Node *Next[26];Node() {num = -1;memset(Next, NULL, sizeof(Next));}
};void trie_add(Node*root, char*S, int d) {int L = strlen(S);Node *p = root;for(int i = 0; i < L; i++) {int id = S[i] - 'a';if(p->Next[id] == NULL) {p->Next[id] = new Node();}p = p->Next[id];}p->num = max(p->num, d);
}void trie_query(Node*root, int pos, int L) {if(dp[pos] < 0) return;Node *p = root;for(int i = pos, j = 1; i < L; i++, j++) {int id = S[i] - 'a';if(p->Next[id] == NULL) {return;}p = p->Next[id];if(p->num >= 0) dp[pos + j] = max(dp[pos + j], dp[pos] + p->num);}
}int main() {int n; //FIN;while(~scanf("%d%s", &n, S)) {memset(dp, -INF, sizeof(dp));dp[0] = 0;Node *root = new Node();for(int i = 1; i <= n; i++) {char word[100]; int d;scanf("%s%d", word, &d);trie_add(root, word, d);}int L = strlen(S);for(int i = 0; i < L; i++) {trie_query(root, i, L);}printf("%d\n", dp[L] < 0 ? -1 : dp[L]);}return 0;
}