HDU 4057 Rescue the Rabbit(11年大连，AC自动机+状态压缩DP)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一些模式串，每个串有一定的价值，现在构造一个长度为M的串，问最大的价值为多少，每个模式串最多统计一次。
http://acm.hdu.edu.cn/showproblem.php?pid=4057
11年大连现场赛的题目，不算非常难。
由于每个模式串最多统计一次，也算是降低了难度，最多10个串，容易想至于状态压缩。
Trie树上的状态最多1000个，100*10，而最终的串长度最多为100
容易想到的DP，dp[i][j][k]，表示长度为i的串，位于Trie上的状态j，模式串的状态为k的最大价值。
这个复杂度为100*1024*1000，题目给了10s，还是可以搞的，但是空间不够，只能用滚动数组了。
先建立Trie树，以及失败指针，对于每一个结点，标号，静态的方便点。
最终DP，通过模式串的状态确定当前价值
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define eps 1e-10#define N 100005#define inf 1<<20#define zero(a) (fabs(a)<eps)#define lson (step<<1)#define rson (step<<1|1)using namespace std;struct Trie{ int next[4],fail; int end; void Init(){next[0]=next[1]=next[2]=next[3]=0;fail=end=0;}}tree[N];int dp[2][1005][1<<10];char str[105];int val[105],tot;int id(char ch){ if(ch=='A') return 0; if(ch=='T') return 1; if(ch=='G') return 2; return 3;}void Insert(char *s,int len,int k){ int p=0; for(int i=0;i<len;i++){ int q=id(s[i]); if(tree[p].next[q]==0){ tree[++tot].Init(); tree[p].next[q]=tot; } p=tree[p].next[q]; } tree[p].end|=(1<<k);}void Bulid_Fail(){ int que[N]; int head=0,tail=0; que[tail++]=0; while(head<tail){ int p=que[head++]; for(int i=0;i<4;i++){ if(tree[p].next[i]==0) tree[p].next[i]=tree[tree[p].fail].next[i]; else{ int q=tree[p].next[i]; if(p) tree[q].fail=tree[tree[p].fail].next[i]; tree[q].end|=tree[tree[q].fail].end; que[tail++]=q; } } }}int n,m;int get(int state){ int ans=0; for(int i=0;i<n;i++) if(state&(1<<i)) ans+=val[i]; return ans;}void DP(){ memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=1;i<=m;i++){ memset(dp[i&1],0,sizeof(dp[i&1])); for(int j=0;j<=tot;j++){ for(int k=0;k<4;k++){ for(int r=0;r<(1<<n);r++){ if(dp[(i+1)&1][j][r]) dp[i&1][tree[j].next[k]][r|tree[tree[j].next[k]].end]=1; } } } } int ans=-inf; for(int j=0;j<(1<<n);j++) for(int i=0;i<=tot;i++) if(dp[m&1][i][j]){ ans=max(ans,get(j)); break; } if(ans<0) puts("No Rabbit after 2012!"); else printf("%d\n",ans);}int main(){ freopen("1.in","r",stdin); freopen("2.out","w",stdout); while(scanf("%d%d",&n,&m)!=EOF){ tree[0].Init();tot=0; for(int i=0;i<n;i++){ scanf("%s%d",str,&val[i]); Insert(str,strlen(str),i); } Bulid_Fail(); DP(); } return 0;}