题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=3341
题目大意：有不超过50个模式串，每个模式串长度不超过10。现在给出一个长度不超过40的串，要求将其重组（即可以打乱字符的顺序），最大化其得分。一个串的得分为：第一个模式串在该串中出现的次数+第二个模式串在该串中出现的次数……，其中每一个模式串可以重叠，如AAA中AA出现了两次。所有串中只有AGCT四种字符，不超过30组数据。
题目分析：我们可以发现：能获得的最大得分只跟匹配串中的AGCT的个数有关。我们对所有模式串建一个trie图，每一个模式串的结尾val++，并且每一个节点P获得它所有fail节点的val，表示如果走到节点P，则已经自动匹配完以它fail结尾的模式串。然后记P->f[x][y][z][w]表示已经用去x个A，y个G，z个C，w个T，转移到它的儿子。
然而我们机智的发现，如果有500个节点，这样开f数组，空间肯定爆炸。考虑到本题中是AGCT的个数之和<=40，而不是每一个都是40，有用的状态顶多11^4个。我们可以用hash的方法将四元组(x,y,z,w)映射到一个一位数组上，这样空间降到500*11^4。
后来我又参考了一下网上大神的题解，发现了一种更为简洁的方法，四元组(x,y,z,w)->x*(ng+1)*(nc+1)*(nt+1)+y*(nc+1)*(nt+1)+z*(nt+1)+w，其中ng,nc,nt分别表示G，C，T的个数。感觉有点像进制或乘法原理，第一位用nt+1进制，第二位用nc+1进制……总之好写了很多。
CODE：
#include<iostream> #include<string> #include<cstring> #include<cmath> #include<cstdio> #include<cstdlib> #include<stdio.h> #include<algorithm> using namespace std; const int maxn=500; const int maxs=11*11*11*11+11; struct Tnode { int f[maxs]; int val; Tnode *son[4],*fsto; } tree[maxn]; Tnode *Root; int cur; Tnode *que[maxn]; int head,tail; int na,ng,nc,nt,ms; char s[maxn][maxn]; int n,cas=0; Tnode *New_node() { cur++; for (int i=0; i<ms; i++) tree[cur].f[i]=-1; tree[cur].val=0; for (int i=0; i<4; i++) tree[cur].son[i]=NULL; tree[cur].fsto=NULL; return tree+cur; } void Insert(char *t) { Tnode *P=Root; int len=strlen(t); for (int i=0; i<len; i++) { int to=0; if (t[i]=='G') to=1; if (t[i]=='C') to=2; if (t[i]=='T') to=3; if (!P->son[to]) P->son[to]=New_node(); P=P->son[to]; } P->val++; } void Init() { for (int i=1; i<=n; i++) scanf("%s",&s[i]); scanf("%s",&s[n+1]); int len=strlen(s[n+1]); na=ng=nc=nt=0; for (int i=0; i<len; i++) { if (s[n+1][i]=='A') na++; if (s[n+1][i]=='G') ng++; if (s[n+1][i]=='C') nc++; if (s[n+1][i]=='T') nt++; } ms=(na+1)*(ng+1)*(nc+1)*(nt+1); cur=-1; Root=New_node(); for (int i=1; i<=n; i++) Insert(s[i]); } void Bfs() { head=0,tail=1; que[tail]=Root; while (head<tail) { Tnode *F=que[++head]; for (int i=0; i<4; i++) if (F->son[i]) { Tnode *P=F->son[i],*Node=F->fsto; while ( Node && !Node->son[i] ) Node=Node->fsto; if (Node) P->fsto=Node->son[i]; else P->fsto=Root; P->val+=P->fsto->val; que[++tail]=P; } } for (int i=0; i<4; i++) if (!Root->son[i]) Root->son[i]=Root; for (int i=2; i<=tail; i++) for (int j=0; j<4; j++) if (!que[i]->son[j]) que[i]->son[j]=que[i]->fsto->son[j]; } void Work(int x,int y,int id) { for (int i=1; i<=tail; i++) { Tnode *P=que[i]; if (P->f[x]!=-1) { int &z=P->son[id]->f[y]; z=max(z,P->f[x]+P->son[id]->val); } } } void DP() { Root->f[0]=0; for (int s=0; s<ms-1; s++) { int t=s; int a=t/((ng+1)*(nc+1)*(nt+1)); t-=(a*(ng+1)*(nc+1)*(nt+1)); int g=t/((nc+1)*(nt+1)); t-=(g*(nc+1)*(nt+1)); int c=t/(nt+1); t-=(c*(nt+1)); if (a<na) Work(s,s+(ng+1)*(nc+1)*(nt+1),0); if (g<ng) Work(s,s+(nc+1)*(nt+1),1); if (c<nc) Work(s,s+(nt+1),2); if (t<nt) Work(s,s+1,3); } int ans=0; for (int i=1; i<=tail; i++) ans=max(ans,que[i]->f[ms-1]); printf("Case %d: %d\n",cas,ans); } int main() { freopen("c.in","r",stdin); freopen("c.out","w",stdout); while ( scanf("%d",&n),n ) { cas++; Init(); Bfs(); DP(); n=0; } return 0; }
