首页 > 代码库 > Hdu 3341 Lost's revenge (ac自动机+dp+hash)
Hdu 3341 Lost's revenge (ac自动机+dp+hash)
题目大意:
给出很多个DNA串,每一个串的价值为1,最后给出一个长串,要你重新排列最后的串使之它所有的子串的权值和最大。
思路分析:
最先容易想到的思路就是搜!管她3721。。直接一个字符一个字符的码,然后在AC自动机上判断最后的权值。TLE哟。
然后发现搜过不去,那就dp咯。再容易想到的就是dp[i][a][b][c][d] 表示此时遍历AC自动机的节点在i,然后构成了a个A,b个G,c个C,d个T的权值。
再一看内存,500*40*40*40*40...然后。。。就没有然后了
再想,因为它说的是这个串的长度是40,所以最多的状态就是10*10*10*10.。,所以开40^4就是浪费。所以要把状态hash下来。
关于hash ...cnt[0]-cnt[3] 表示ACGT的数量。 现在表示ABCD个ACGT 就是A*(cnt[3]+1)*(cnt[2]+1)*(cnt[1]+1)+B*(cnt[2]+1)*(cnt[1]+1)+C*(cnt[1]+1)+D*1
然后就按照上面的五维dp去做就好啦。坑点就是。。又有重复的串,人与人之间最基本的信任都没有。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <utility> #define inf 0x3f3f3f3f #include <vector> using namespace std; const char tab = 0; const int max_next = 4; int idx; struct trie { struct trie *fail; struct trie *next[max_next]; int isword; int index; }; int rev[256]; trie *que[100005],ac[100005]; int head,tail; trie *New() { trie *temp=&ac[idx]; for(int i=0;i<max_next;i++)temp->next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp; } void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i<len;i++){ if(t->next[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } t->isword++; } void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head<tail){ trie *temp=que[head++],*p; for(int i=0;i<max_next;i++){ if(temp->next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword)temp->next[i]->isword+=temp->next[i]->fail->isword; que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } } } void del() { for(int i=0;i<idx;i++) free(&ac[i]); } void tra() { for(int i=0;i<idx;i++) { if(ac[i].fail!=NULL)printf("fail = %d ",ac[i].fail->index); for(int k=0;k<max_next;k++) printf("%d ",ac[i].next[k]->index); puts(""); } } char word[50]; int cnt[5]; int dp[515][11*11*11*11+5]; int bit[5]; int solve() { memset(dp,-1,sizeof dp); dp[0][0]=0; bit[0]=(cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1); bit[1]=(cnt[2]+1)*(cnt[3]+1); bit[2]=(cnt[3]+1); bit[3]=1; for(int A=0;A<=cnt[0];A++) { for(int B=0;B<=cnt[1];B++) { for(int C=0;C<=cnt[2];C++) { for(int D=0;D<=cnt[3];D++) { int state=A*bit[0]+B*bit[1]+C*bit[2]+D*bit[3]; for(int i=0;i<idx;i++) { if(dp[i][state]>=0) { for(int k=0;k<4;k++) { if(k==0 && A==cnt[0])continue; if(k==1 && B==cnt[1])continue; if(k==2 && C==cnt[2])continue; if(k==3 && D==cnt[3])continue; dp[ac[i].next[k]->index][state+bit[k]]=max(dp[ac[i].next[k]->index][state+bit[k]],dp[i][state]+ac[i].next[k]->isword); } } } } } } } int ans=0; int tag=cnt[0]*bit[0]+cnt[1]*bit[1]+cnt[2]*bit[2]+cnt[3]*bit[3]; for(int i=0;i<idx;i++) ans=max(ans,dp[i][tag]); return ans; } int main() { rev['A']=0; rev['C']=1; rev['G']=2; rev['T']=3; int n,cas=1; while(scanf("%d",&n)!=EOF && n) { idx=0; trie *root = New(); for(int i=1;i<=n;i++) { scanf("%s",word); Insert(root,word,strlen(word)); } acbuild(root); scanf("%s",word); int len=strlen(word); memset(cnt,0,sizeof cnt); for(int j=0;j<len;j++) cnt[rev[word[j]]]++; printf("Case %d: %d\n",cas++,solve()); } return 0; }
Hdu 3341 Lost's revenge (ac自动机+dp+hash)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。