好贷网好贷款

字典树 + DP

发布时间:2016-12-4 1:54:16 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"字典树 + DP",主要涉及到字典树 + DP方面的内容,对于字典树 + DP感兴趣的同学可以参考一下。

http://www.acdream.tk/problem.php?cid=1001&pid=1  dp[i] 表示匹配前i个字符的最大权值 View Code #include<stdio.h>#include<string.h>#include<queue>using namespace std;class trie{public : int num; trie* child[27]; trie() { num=0; memset(child,0,sizeof(child)); }}root;void insert(char *s,int id){ class trie *cur=&root; int len=strlen(s); for(int i=0;i<len;i++) { int id=s[i]-'a'; if(!cur->child[id]) cur->child[id]=new trie; cur=cur->child[id]; } cur->num=id;}queue<int> Q;void find(char *s){ while(!Q.empty()) Q.pop(); class trie *cur=&root; for(int i=0;s[i];i++) { int id=s[i]-'a'; if(!cur->child[id]) return ; cur=cur->child[id]; if(cur->num) Q.push(cur->num); }}void init(trie* T){ int i; for(i=0;i<26;i++) { if(T->child[i]) init(T->child[i]); } T->num=0; for(i=0;i<26;i++) T->child[i]=0;}int max(int a,int b){ return a>b?a:b;}char s[10010];char ss[50];int w[1010];int dp[10100];int length[1010];int main(){ int i,j,n; while(scanf("%d%s",&n,s+1)!=EOF) { class trie* cur=&root; init(cur); int len=strlen(s+1); for(i=1;i<=n;i++) { scanf("%s%d",ss,&w[i]); length[i]=strlen(ss); insert(ss,i); } memset(dp,-1,sizeof(dp)); dp[0]=0; for(i=1;i<=len;i++)if(dp[i-1]!=-1) { find(s+i); while(!Q.empty()) { j=Q.front();Q.pop(); dp[i+length[j]-1]=max(dp[i+length[j]-1],dp[i-1]+w[j]); } } printf("%d\n",dp[len]); } return 0;}

上一篇:poj 2662 A Walk Through the Forest
下一篇:poj 3498 网络流 拆点

相关文章

关键词: 字典树 + DP

相关评论