很直白，很实在，很炫酷的一道题。
dp[i][j][k] 表示长度为 i 时，最后一位在自动机的第 j 个状态点，已经包含了状态 k 的字符串的最优解。
然后dp[i][j][k] 可以转移到 四个位置 即在i+1位放置‘A’,‘G’,’C’,’T’，，j显然会在自动机走，k根据 j 的变化而变化。
最后答案为 dp[ l ][ j ][ k ]的最大值。
内存卡的比较厉害，可以用滚动数组。
不过提说现场赛内存是没有上限的，不知道是不是HDU故意的233。
#include <iostream>#include<time.h>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<string>#include<map>#include<vector>#include <algorithm>#include <queue>#include <cmath>#define LL long long#define ULL unsigned long longusing namespace std;const int MAXS = 4,MAXN = 1010;const int MATN = 70;struct MAT{int row,col;ULL mat[MATN][MATN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1; i <= row; ++i)for(int j = 1; j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,LL MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(k = 1; k <= this->col; ++k)for(i = 1; i <= tmp.row; ++i)for(j = 1; j <= tmp.col; ++j)tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j]);return tmp;}MAT Quick(LL n,LL MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1; i <= row; ++i){for(j = 1; j <= col; ++j)printf("%3lld ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};struct Trie{int next[MAXS];int fail;int flag;} st[MAXN];queue<int> q;struct ACautomaton{int Top,root;int Creat(){memset(st[Top].next,-1,sizeof(st[Top].next));st[Top].flag = -1;st[Top].fail = -1;return Top++;}void Init(){Top = 0;root = Creat();}inline int CalIndex(char c){if(c == 'A')return 0;if(c == 'G')return 1;if(c == 'C')return 2;return 3;}void Insert(char *s,int ty){int i = 0,tr = root,tmp;while(s[i] != '\0'){tmp = CalIndex(s[i]);if(st[tr].next[tmp] == -1)st[tr].next[tmp] = Creat();tr = st[tr].next[tmp],++i;}st[tr].flag = ty;}void GetFail(){st[root].fail = -1;q.push(root);int f,t;while(q.empty() == false){f = q.front();q.pop();for(int i = 0; i < MAXS; ++i){if(st[f].next[i] != -1){t = st[f].fail;while(t != -1 && st[t].next[i] == -1)t = st[t].fail;if(t == -1)st[st[f].next[i]].fail = root;elsest[st[f].next[i]].fail = st[t].next[i];q.push(st[f].next[i]);}}}}int OverLapMatch(char *s){int i ,tr = root,tmp;int ans = 0;for(i = 0; s[i] != '\0'; ++i){tmp = CalIndex(s[i]);while(tr != -1 && st[tr].next[tmp] == -1 )tr = st[tr].fail;if(tr == -1){tr = root;continue;}tr = st[tr].next[tmp];tmp = tr;while(tmp != root && st[tmp].flag != -1){if(st[tmp].flag)ans++;tmp = st[tmp].fail;}}return ans;}};int val[11];char s[1010];int dp[2][1025][1002];int main(){ // freopen("data1.in","r",stdin);int n,m,i,j,k,l,p;ACautomaton AC;while(scanf("%d %d",&n,&m) != EOF){AC.Init();for(i = 1; i <= n; ++i){scanf("%s %d",s,&val[i]);if(strlen(s) <= m)AC.Insert(s,i-1);}AC.GetFail();memset(dp,0x88,sizeof(dp));dp[0][0][0] = 0;int tr,Max = -10000,tmp,sta;int SumSta = (1<<n);for(p = 0; p < m; ++p){i = (p&1);memset(dp[i^1],0x88,sizeof(dp[i^1]));for(j = 0; j < SumSta; ++j){for(k = 0; k < AC.Top; ++k){if(dp[i][j][k] < -1000)continue;for(l = 0; l < 4; ++l){tr = k;sta = j;tmp = dp[i][j][k];while(tr != -1){if(st[tr].next[l] != -1 && st[st[tr].next[l]].flag != -1){if((sta&(1<<st[st[tr].next[l]].flag)) == 0){sta |= (1<<st[st[tr].next[l]].flag);tmp += val[st[st[tr].next[l]].flag + 1];}}tr = st[tr].fail;}tr = k;while(tr != -1){if(st[tr].next[l] != -1)break;tr = st[tr].fail;}if(tr == -1)tr = 0;elsetr = st[tr].next[l];dp[i^1][sta][tr] = max(tmp,dp[i^1][sta][tr]);}}}}for(j = 0; j < SumSta; ++j){for(k = 0; k < AC.Top; ++k){Max = max(Max,dp[m&1][j][k]);}}if(Max < 0)puts("No Rabbit after 2012!");elseprintf("%d\n",Max);}return 0;}
千万个不眠的夜里，你一直让我感动，只是因为相信有个人会爱我一生一世。
