首页 > 代码库 > HNU 13108 Just Another Knapsack Problem ac自动机上的dp
HNU 13108 Just Another Knapsack Problem ac自动机上的dp
题目链接:点击打开链接
题目链接:
给定一个母串。
给出n个子串和子串对应的价值
用下面的n个子串拼出母串,则得到的价值为子串价值和
拼接时不能有重叠遗漏(即母串的每个位置恰好被覆盖一次)
在ac自动机上找的时候搞一个dp数组就好了
#include<stdio.h> #include<iostream> #include<cmath> #include<cstring> #include<queue> using namespace std; const int maxnode = 250*1000+10000; const int sigma_size = 26; struct Trie{ int dp[101000]; int ch[maxnode][sigma_size]; int val[maxnode]; //该单词在模式串中出现的最大价值 int last[maxnode]; int f[maxnode]; //失配数组 int pre[maxnode]; //该单词的前驱 int len[maxnode]; //以该单词结尾的单词长度 int Char[maxnode]; //该单词对应的字母 int road[maxnode]; //路径压缩优化 针对计算模式串出现的种数 int sz; int Newnode() { val[sz] = f[sz] = last[sz] = len[sz] = 0; memset(ch[sz], 0, sizeof ch[sz]); return sz++; } void init(){ sz=0; Newnode(); } int idx(char c){ return c-'a'; } int insert(char *s, int v){ int u = 0; for(int i = 0, c; s[i] ;i++){ c = idx(s[i]); if(!ch[u][c]) ch[u][c] = Newnode(); pre[ch[u][c]] = u; Char[ch[u][c]] = s[i]; len[ch[u][c]] = len[u]+1; u = ch[u][c]; } val[u] = max(val[u], v); return u; } void getFail(){ queue<int> q; for(int i = 0; i<sigma_size; i++) if(ch[0][i]) q.push(ch[0][i]); int r, c, u, v; while(!q.empty()){ r = q.front(); q.pop(); for(c = 0; c<sigma_size; c++){ u = ch[r][c]; if(!u)continue; q.push(u); v = f[r]; while(v && ch[v][c] == 0) v = f[v]; //沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环 f[u] = ch[v][c]; } } } void find(char *T){ int j = 0; for(int i = 0, c, temp; T[i] ; i++){ dp[i] = 0; c = idx(T[i]); while(j && ch[j][c]==0) j = f[j]; j = ch[j][c]; temp = j; while(temp){ if(val[temp]){ if(i-len[temp] < 0) dp[i] = max(dp[i], val[temp]); else if(dp[i-len[temp]]) dp[i] = max(dp[i], dp[i-len[temp]]+val[temp]); } temp = f[temp]; } // puts(""); } } }ac; char s[100100], t[350]; void input(){ int n, val; cin>>n; ac.init(); while(n--){ scanf("%s %d", t, &val); ac.insert(t, val); } } int main(){ while(~scanf("%s", s)){ input(); ac.getFail(); ac.find(s); printf("%d\n", ac.dp[strlen(s)-1]); } return 0; }
HNU 13108 Just Another Knapsack Problem ac自动机上的dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。