3 AC CG GT CGAT 1 AA AAA 0
Case 1: 3 Case 2: 2
题意：给定n个特定的串，最后给定一个串，让重新组合，使得含有的上面特定的串最多。
首先肯定需要建立ac自动机，然后就是dp，这道题在dp的时候需要一定的处理，不能直接搞，学习别人的思路，采用hash的方法，将死个字符出现的次数映射成数字，且保证了不会出现状态的重复，好神奇，然后就是一个dp的过程了。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-2-7 0:28:06
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Trie{
int next[550][4],fail[550],end[550];
int root,L;
int newnode(){
for(int i=0;i<4;i++)
next[L][i]=-1;
end[L++]=0;
return L-1;
}
void init(){
L=0;
root=newnode();
}
int id(char ch){
if(ch==‘A‘)return 0;
if(ch==‘T‘)return 1;
if(ch==‘C‘)return 2;
return 3;
}
void insert(char *str){
int len=strlen(str);
int now=root;
for(int i=0;i<len;i++){
int p=id(str[i]);
if(next[now][p]==-1)
next[now][p]=newnode();
now=next[now][p];
}
end[now]++;
}
void build(){
queue<int> q;
fail[root]=root;
for(int i=0;i<4;i++){
if(next[root][i]==-1)
next[root][i]=root;
else {
fail[next[root][i]]=root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now=q.front();
q.pop();
end[now]+=end[fail[now]];
for(int i=0;i<4;i++){
if(next[now][i]==-1)
next[now][i]=next[fail[now]][i];
else {
fail[next[now][i]]=next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
int dp[11*11*11*11+10][550];
int num[5],ss[5],hash[6];
int solve(char *str){
memset(hash,0,sizeof(hash));
memset(num,0,sizeof(num));
int len=strlen(str);
for(int i=0;i<len;i++)
num[id(str[i])]++;
hash[3]=1;
hash[2]=hash[3]*(num[3]+1);
hash[1]=hash[2]*(num[2]+1);
hash[0]=hash[1]*(num[1]+1);
int t=hash[0]*num[0]+hash[1]*num[1]+hash[2]*num[2]+hash[3]*num[3];
memset(dp,-1,sizeof(dp));
int ans=dp[0][0]=0;
for(int i=0;i<=t;i++){
ss[0]=i/hash[0];
ss[1]=(i%hash[0])/hash[1];
ss[2]=(i%hash[1])/hash[2];
ss[3]=(i%hash[2])/hash[3];
if(ss[0]>num[0]||ss[1]>num[1]||ss[2]>num[2]||ss[3]>num[3])continue;
for(int j=0;j<L;j++){
if(dp[i][j]==-1)continue;
for(int k=0;k<4;k++){
int tt=next[j][k];
if(ss[k]<num[k]&&dp[i+hash[k]][tt]<dp[i][j]+end[tt])
dp[i+hash[k]][tt]=dp[i][j]+end[tt];
}
}
}
for(int i=0;i<L;i++)
ans=max(ans,dp[t][i]);
return ans;
}
}ac;
char str[100010];
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m,n,T=0;
while(~scanf("%d",&n)){
if(n==0)break;
ac.init();
while(n--){
scanf("%s",str);
ac.insert(str);
}
ac.build();
scanf("%s",str);
printf("Case %d: %d\n",++T,ac.solve(str));
}
return 0;
}
原文：http://blog.csdn.net/xianxingwuguan1/article/details/18955665