首页 > 代码库 > HNU 13108 Just Another Knapsack Problem DP + Trie树优化
HNU 13108 Just Another Knapsack Problem DP + Trie树优化
题意：
给你一个文本串，和一些模式串，每个模式串都有一个价值，让你选一些模式串来组成文本串，使获得的价值最大。每个模式串不止能用一次。
思路：
多重背包，枚举文本串的每个位置和模式串，把该模式串拼接在当前位置，看下一个位置是否能得到更优值。但是，存在很多模式串不能拼在当前位置的，无效状态。所以可以用Trie树来优化转移。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <string>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <functional>#include <cctype>#include <time.h>using namespace std;const int INF = 1<<30;const int MAXN = 1e5+5;const int MAXLEN = 333;const int MAXNODE = 1e5+5;;struct Trie { int ch[MAXNODE][26]; int val[MAXNODE], use; inline void init() { for (int i = 0; i < 26; i++) ch[0][i] = 0; val[0] = 0; use = 1; } inline int New() { for (int i = 0; i < 26; i++) ch[use][i] = 0; val[use] = 0; return use++; } inline int idx(char c) { return c - ‘a‘; } void insert(char str[], int v) { int len = strlen(str); int p = 0; for (int i = 0; i < len; i++) { int c = idx(str[i]); if (!ch[p][c]) ch[p][c] = New(); p = ch[p][c]; } val[p] = max(val[p], v); } int solve(char S[], int dp[]) { int len = strlen(S); for (int i = 0; i <= len; i++) dp[i] = -1; dp[0] = 0; for (int i = 0; i < len; i++) { if (dp[i]<0) continue; for (int j = i, p = 0; j <= len; j++) { int c = idx(S[j]); if (val[p]) dp[j] = max(dp[j], dp[i]+val[p]); p = ch[p][c]; if (p==0) break; } } return max(dp[len], 0); }};Trie solver;char S[MAXN], P[MAXLEN];int dp[MAXN];int m, v;int main() { #ifdef Phantom01 freopen("HNU13108.txt", "r", stdin); #endif //Phantom01 while (scanf("%s", S)!=EOF) { scanf("%d", &m); solver.init(); for (int i = 0; i < m; i++) { scanf("%s%d", P, &v); solver.insert(P, v); } printf("%d\n", solver.solve(S, dp)); } return 0;}
HNU 13108 Just Another Knapsack Problem DP + Trie树优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。