题目是给一个DNA重新排列使其包含最多的数论基因。

考虑到内存大概就只能这么表示状态：

dp[i][A][C][G][T]，表示包含各碱基个数为ACGT且当前后缀状态为自动机第i的结点的字符串最多的数论基因数

其中ACGT可以hash成一个整数（a*C*G*T+c*G*T+g*T+T），这样用二维数组就行了，而第二维最多也就11*11*11*11个。

接下来转移依然是我为人人型，我是丢进一个队列，用队列来更新状态的值。

这题果然挺卡常数的，只好手写队列，最后4500msAC，还是差点超时，代码也搞得挺乱的。

1 #include
     
       2 #include
      
        3 using namespace std; 4 int tn,ch[555][4],fail[555],flag[555]; 5 int idx[128]; 6 void insert(char *s){ 7     int x=0; 8     for(int i=0; s[i]; ++i){ 9         int y=idx[s[i]];10         if(ch[x][y]==0) ch[x][y]=++tn;11         x=ch[x][y];12     }13     ++flag[x];14 }15 int que[555];16 void init(){17     memset(fail,0,sizeof(fail));18     int front=0,rear=0;19     for(int i=0; i<4; ++i){20         if(ch[0][i]) que[rear++]=ch[0][i];21     }22     while(front!=rear){23         int x=que[front++];24         for(int i=0; i<4; ++i){25             if(ch[x][i]) que[rear++]=ch[x][i],fail[ch[x][i]]=ch[fail[x]][i],flag[ch[x][i]]+=flag[ch[fail[x]][i]];26             else ch[x][i]=ch[fail[x]][i];27         }28     }29 }30 int d[555][14641];31 int quex[555*14641],quey[555*14641];32 int main(){33     idx['A']=0; idx['C']=1; idx['G']=2; idx['T']=3;34     char str[44];35     int n,cse=0;36     while(~scanf("%d",&n) && n){37         tn=0;38         memset(ch,0,sizeof(ch));39         memset(flag,0,sizeof(flag));40         while(n--){41             scanf("%s",str);42             insert(str);43         }44         init();45         scanf("%s",str);46         int times[4]={
   0};47         for(int i=0; str[i]; ++i){48             ++times[idx[str[i]]];49         }50         int tcal0=(times[1]+1)*(times[2]+1)*(times[3]+1);51         int tcal1=(times[2]+1)*(times[3]+1);52         int tcal2=(times[3]+1);53         memset(d,-1,sizeof(d));54         d[0][0]=0;55         int front=0,rear=0,x,y,ny,cnt[4];56         quex[rear]=0; quey[rear]=0; ++rear;57         while(front!=rear){58             x=quex[front]; y=quey[front]; ++front;59             ny=y;60             cnt[0]=ny/tcal0;61             ny-=cnt[0]*tcal0;62             cnt[1]=ny/tcal1;63             ny-=cnt[1]*tcal1;64             cnt[2]=ny/tcal2;65             cnt[3]=ny-cnt[2]*tcal2;66             for(int i=0; i<4; ++i){67                 if(cnt[i]>=times[i]) continue;68                 ++cnt[i];69                 ny=cnt[0]*tcal0+cnt[1]*tcal1+cnt[2]*tcal2+cnt[3];70                 if(d[ch[x][i]][ny]==-1){71                     d[ch[x][i]][ny]=d[x][y]+flag[ch[x][i]];72                     quex[rear]=ch[x][i]; quey[rear]=ny; ++rear;73                 }else if(d[ch[x][i]][ny]