题意：N个子串，每个串价值为1，给你一个长串S，求重排后最大的价值（可重叠）；
明白题意后，很裸的自动机+DP，建完自动机状态表示成dp[2][500][20][20][20]，把其中3个必然小于20的元素来DP，然后TLE，40*500*20*20*20，有30组case，必然TLE；
View Code
1 /* 2 学习一：一种压缩方式，类似于进制表示，每个元素的个数确定后 3 num[],那么bas[0]=1,bas[1]=bas[i-1]*(num[i-1]+1); 4 例如num[]={2,1,3,2};bas[]={1,3,6,24}; 5 编码 incode() ret+=num[i]*bas[i]; 6 然后就是解码 decode(); 7 这样把20^3*40的空间压缩成11^4的空间； 8 但是还是TLE；40*500*4*11^4*30; 9 我们发现状态的转移都是从长度为n-1转移到n; 10 而长度为n-1的编码一定是小于长度为n的编码的； 11 类似于1100->1101或1110数值都是变大的； 12 所以直接从编码小的转移到编码大的就可以了， 13 500*11^4*4*30 AC; 14 */ 15 //18:34 16 #include<cstdio> 17 #include<cstring> 18 #include<cstdlib> 19 #include<iostream> 20 #include<algorithm> 21 #include<cmath> 22 #include<queue> 23 #include<map> 24 using namespace std; 25 const int N=500+10; 26 const int SZ=4; 27 int idx(char s){ 28 if (s=='A') return 0; 29 if (s=='G') return 1; 30 if (s=='T') return 2; 31 return 3; 32 } 33 struct AC{ 34 int ch[N][SZ]; 35 int sz,f[N],match[N]; 36 queue<int> q; 37 void init(){ 38 sz=1;memset(match,0,sizeof(match)); 39 memset(ch[0],0,sizeof(ch[0])); 40 } 41 void insert(char *s){ 42 int m=strlen(s),rt=0; 43 for (int i=0;i<m;i++){ 44 int c=idx(s[i]); 45 if (ch[rt][c]==0){ 46 ch[rt][c]=sz; 47 memset(ch[sz],0,sizeof(ch[sz])); 48 sz++; 49 } 50 rt=ch[rt][c]; 51 } 52 match[rt]+=1; 53 } 54 void getfail(){ 55 while (!q.empty()) q.pop(); 56 for (int i=0;i<SZ;i++){ 57 int c=ch[0][i]; 58 if (c){ f[c]=0;q.push(c); } 59 } 60 while(!q.empty()){ 61 int u=q.front();q.pop(); 62 for (int i=0;i<SZ;i++){ 63 int r=ch[u][i]; 64 if(!r){ 65 ch[u][i]=ch[f[u]][i]; 66 }else { 67 q.push(r); 68 int v=f[u]; 69 f[r]=ch[v][i]; 70 match[r]+=match[f[r]]; 71 } 72 } 73 } 74 } 75 void find(){ 76 cout<<"----------- "<<endl; 77 for (int i=0;i<sz;i++){ 78 if (match[i]) cout<<i<<" "<<match[i]<<endl; 79 } 80 cout<<"+++++++++++ "<<endl; 81 } 82 }H; 83 /////////////////////AC自动机部分/////////////////////// 84 char T[50]; 85 int up[10]; 86 int bas[10]; 87 void init(){ 88 scanf("%s",T); 89 memset(up,0,sizeof(up)); 90 for (int i=0;T[i];i++){ 91 int c=idx(T[i]); 92 up[c]++; 93 } 94 bas[0]=1; 95 for (int i=1;i<=4;i++){ 96 bas[i]=bas[i-1]*(up[i-1]+1); 97 } 98 /* cout<<"*** "<<endl; 99 for (int i=0;i<=4;i++){ 100 cout<<bas[i]<<" "; 101 }cout<<endl; 102 cout<<"/// "<<endl; 103 */ 104 } 105 int dp[15000][N]; 106 void decode(int *num,int k){ 107 for (int i=3;i>=0;i--){ 108 num[i]=k/bas[i]; 109 k=k%bas[i]; 110 } 111 } 112 void Max(int &x,int y){ 113 if (x==-1) { 114 x=y; 115 }else { 116 x=max(x,y); 117 } 118 } 119 void DP(){ 120 memset(dp,-1,sizeof(dp)); 121 dp[0][0]=0; 122 int num[10]; 123 for (int i=0;i<bas[4];i++){ 124 decode(num,i); 125 for (int j=0;j<H.sz;j++){ 126 if (dp[i][j]!=-1){ 127 for (int k=0;k<SZ;k++){ 128 int c=H.ch[j][k]; 129 if (num[k]<up[k]){ 130 int t=i+bas[k]; 131 Max(dp[t][c],dp[i][j]+H.match[c]); 132 } 133 } 134 } 135 } 136 } 137 138 int ret=-1,all=bas[4]-1; 139 for (int i=0;i<H.sz;i++){ 140 if (dp[all][i]!=-1) Max(ret,dp[all][i]); 141 } 142 printf("%d\n",ret); 143 } 144 int n; 145 char p[15]; 146 int main(){ 147 int cas=0; 148 while (~scanf("%d",&n),n){ 149 H.init(); 150 for (int i=0;i<n;i++){ 151 scanf("%s",p); 152 H.insert(p); 153 } 154 H.getfail(); 155 // 156 // H.find(); 157 // 158 init(); 159 printf("Case %d: ",++cas); 160 DP(); 161 } 162 return 0; 163 }