HDU P3341 Lost’s revenge 题解+数据生成器

大家好，又见面了，我是你们的朋友全栈君。

Lost and AekdyCoin are friends. They always play “number game”(A boring game based on number theory) together. We all know that AekdyCoin is the man called “nuclear weapon of FZU,descendant of Jingrun”, because of his talent in the field of number theory. So Lost had never won the game. He was so ashamed and angry, but he didn’t know how to improve his level of number theory.

One noon, when Lost was lying on the bed, the Spring Brother poster on the wall(Lost is a believer of Spring Brother) said hello to him! Spring Brother said, “I’m Spring Brother, and I saw AekdyCoin shames you again and again. I can’t bear my believers were being bullied. Now, I give you a chance to rearrange your gene sequences to defeat AekdyCoin!”.

It’s soooo crazy and unbelievable to rearrange the gene sequences, but Lost has no choice. He knows some genes called “number theory gene” will affect one “level of number theory”. And two of the same kind of gene in different position in the gene sequences will affect two “level of number theory”, even though they overlap each other. There is nothing but revenge in his mind. So he needs you help to calculate the most “level of number theory” after rearrangement.

　　　　　　　　　　　　　　——by HDU;

http://acm.hdu.edu.cn/showproblem.php?pid=3341

就是，有N个由’A’C’G’T’构成的KEY串，给一个可以改变顺序的word串，求最多匹配（KEY可重复使用）

AC自动机+DP

f[i][num0][num1][num2][num3]

表示当前在AC自动机i点，’A’用了num0个，’C’用了num1个……

于是她可以转移到她的所有子节点及子节点的fail链上

但是显然因为num0~3他们的范围的问题（你只能每个都开到word串的长这么大，就是40），这样会MLE（自己算算咯）

发现数组开的很冗余；

于是考虑状态压缩（还是hash？？？）

反正把num0~num3压到数组的一维里，对num0而言每个1在压缩后为该维贡献1（sum0=1），对num1而言每个1在压缩后则为该维贡献1*(num0+1)（sum1=num0+1）,对num1而言每个1在压缩后则为该维贡献1*(num1+1)*sum1（sum2=(num1+1)*sum1）…….

这样把原状态的后4维按权（sum）压到一维里

可以看出，这样压缩后不会有多余的空间；

那么开出的数组就是点数i*(num0+1)*(num1+1)*(num2+1)*(num3+1)（组合数学吧）

最大也就num0~3均取10——也不是很大呢

代码如下：

  1 #include<cstdio>
  2 #include<cstring>
  3 using namespace std;
  4 struct ss{
  5     int ch[4];
  6 }x[1000];
  7 int n,tot;
  8 int is_end[510],fail[510];
  9 int que[1000000];
 10 char key[15],word[45];
 11 int num[4],sum[4],f[510][15001];
 12 int boo(int ,int ,int ,int ,int );
 13 void bfs_fail();
 14 int dp();
 15 int pd(char );
 16 int main(){
 17     int i,j,k,len,T=0;
 18     while(1){
 19         scanf("%d",&n);
 20         if(!n)
 21             return 0;
 22         tot=0;
 23         memset(is_end,0,sizeof(is_end));
 24         memset(fail,0,sizeof(fail));
 25         memset(x,0,sizeof(x));
 26         for(i=0;i<=3;i++)
 27             num[i]=0,sum[i]=0;
 28         for(i=1;i<=n;i++){
 29             scanf("%s",key);
 30             len=strlen(key)-1;k=0;
 31             for(j=0;j<=len;j++){
 32                 if(!x[k].ch[pd(key[j])])
 33                     x[k].ch[pd(key[j])]=++tot;
 34                 k=x[k].ch[pd(key[j])];
 35             }
 36             is_end[k]++;
 37         }
 38         bfs_fail();
 39         scanf("%s",word);len=strlen(word)-1;
 40         for(i=0;i<=len;i++)
 41             num[pd(word[i])]++;
 42         sum[0]=1;
 43         for(i=1;i<=3;i++)sum[i]=sum[i-1]*(num[i-1]+1);
 44         printf("Case %d: %d\n",++T,dp());
 45     }
 46     return 0;
 47 }
 48 int boo(int i,int j,int k,int l,int p){
 49     int x;
 50     switch (p){
 51         case 0:x=i;break;
 52         case 1:x=j;break;
 53         case 2:x=k;break;
 54         case 3:x=l;break;
 55     }
 56     if(num[p]-x-1>=0)
 57         return 1;
 58     return 0;
 59 }
 60 void bfs_fail(){
 61     int h=0,t=1,i,j,k;
 62     while(h<t){
 63         ++h;
 64         for(i=0;i<=3;i++)
 65             if(x[que[h]].ch[i]){
 66                 j=que[h];
 67                 while(1){
 68                     if(x[j].ch[i]&&j!=que[h]){
 69                         fail[x[que[h]].ch[i]]=x[j].ch[i];
 70                         break;
 71                     }
 72                     else{
 73                         if(!j)
 74                             break;
 75                         j=fail[j];
 76                     }
 77                 }
 78                 que[++t]=x[que[h]].ch[i];
 79             }
 80     }
 81 }
 82 int dp(){
 83     memset(f,-1,sizeof(f));f[0][0]=0;
 84     int i,j,k,l,o,p,q,r,ans=-1;
 85     for(i=0;i<=num[0];i++)
 86         for(j=0;j<=num[1];j++)
 87             for(k=0;k<=num[2];k++)
 88                 for(l=0;l<=num[3];l++)
 89                     for(o=0;o<=tot;o++)
 90                         if(f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]!=-1)
 91                             for(p=0;p<=3;p++)
 92                                 if(x[o].ch[p]&&boo(i,j,k,l,p)){
 93                                     r=x[o].ch[p];q=0;
 94                                     while(r){
 95                                         q+=is_end[r];
 96                                         r=fail[r];
 97                                     }
 98                                     r=x[o].ch[p];
 99                                     while(1){
100                                         f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]=f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]>f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]+q?f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]:f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]+q;
101                                         if(!r)break;
102                                         r=fail[r];
103                                     }
104                                 }
105     q=sum[0]*num[0]+sum[1]*num[1]+sum[2]*num[2]+sum[3]*num[3];
106     for(i=0;i<=tot;i++)
107         for(j=0;j<=q;j++)
108             if(ans<f[i][j])
109                 ans=f[i][j];
110     return ans;
111 }
112 int pd(char a){
113     int i;
114     switch (a) {
115         case 'A':i=0;break;
116         case 'C':i=1;break;
117         case 'G':i=2;break;
118         case 'T':i=3;break;
119     }
120     return i;
121 }

由于本人也在这个题上卡了好久，故放上数据生成器：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
char s[4]={
    
    'A','C','G','T'};
int main()
{
    freopen("input.txt","w",stdout);
    srand(time(0));
    int T=50,n,l;
    for(int i=1;i<=T;i++){
        n=rand()%5+1;
        printf("%d\n",n);
        for(int j=1;j<=n;j++){
            l=rand()%5+1;
            for(int k=1;k<=l;k++)
                printf("%c",s[rand()%4]);
            printf("\0");printf("\n");
        }
        l=rand()%20+1;
            for(int k=1;k<=l;k++)
                printf("%c",s[rand()%4]);
            printf("\0");printf("\n");
    }
    printf("0");
}