标题效果：

举个很多种DNA弦，每个字符串值值至1。最后，一个长字符串。要安排你最后一次另一个字符串，使其没事子值和最大。

IDEAS：

首先easy我们的想法是想搜索的！管她3721。。直接一个字符一个字符的码，然后在AC自己主动机上推断最后的权值。TLE哟。

然后发现搜过不去。那就dp咯。再easy想到的就是dp[i][a][b][c][d] 表示此时遍历AC自己主动机的节点在i，然后构成了a个A，b个G，c个C。d个T的权值。

再一看内存，500*40*40*40*40...然后。。。就没有然后了

再想，由于它说的是这个串的长度是40。所以最多的状态就是10*10*10*10.。，所以开40^4就是浪费。所以要把状态hash下来。

关于hash ...cnt[0]-cnt[3] 表示ACGT的数量。  如今表示ABCD个ACGT  就是A*(cnt[3]+1)*(cnt[2]+1)*(cnt[1]+1)+B*(cnt[2]+1)*(cnt[1]+1)+C*(cnt[1]+1)+D*1

然后就依照上面的五维dp去做就好啦。

坑点就是。

。又有反复的串，人与人之间最主要的信任都没有。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define inf 0x3f3f3f3f#include 
          
           using namespace std;const char tab = 0;const int max_next = 4;int idx;struct trie{ struct trie *fail; struct trie *next[max_next]; int isword; int index;};int rev[256];trie *que[100005],ac[100005];int head,tail;trie *New(){ trie *temp=&ac[idx]; for(int i=0;i
           
            next[i]=NULL; temp->fail=NULL; temp->isword=0; temp->index=idx++; return temp;}void Insert(trie *root,char *word,int len){ trie *t=root; for(int i=0;i
            
             next[rev[word[i]]]==NULL) t->next[rev[word[i]]]=New(); t=t->next[rev[word[i]]]; } t->isword++;}void acbuild(trie *root){ int head=0,tail=0; que[tail++]=root; root->fail=NULL; while(head
             
              next[i]){ if(temp==root)temp->next[i]->fail=root; else { p=temp->fail; while(p!=NULL){ if(p->next[i]){ temp->next[i]->fail=p->next[i]; break; } p=p->fail; } if(p==NULL)temp->next[i]->fail=root; } if(temp->next[i]->fail->isword)temp->next[i]->isword+=temp->next[i]->fail->isword; que[tail++]=temp->next[i]; } else if(temp==root)temp->next[i]=root; else temp->next[i]=temp->fail->next[i]; } }}void del(){ for(int i=0;i
              
               index); for(int k=0;k
               
                index); puts(""); }}char word[50];int cnt[5];int dp[515][11*11*11*11+5];int bit[5];int solve(){ memset(dp,-1,sizeof dp); dp[0][0]=0; bit[0]=(cnt[1]+1)*(cnt[2]+1)*(cnt[3]+1); bit[1]=(cnt[2]+1)*(cnt[3]+1); bit[2]=(cnt[3]+1); bit[3]=1; for(int A=0;A<=cnt[0];A++) { for(int B=0;B<=cnt[1];B++) { for(int C=0;C<=cnt[2];C++) { for(int D=0;D<=cnt[3];D++) { int state=A*bit[0]+B*bit[1]+C*bit[2]+D*bit[3]; for(int i=0;i
                
                 =0) { for(int k=0;k<4;k++) { if(k==0 && A==cnt[0])continue; if(k==1 && B==cnt[1])continue; if(k==2 && C==cnt[2])continue; if(k==3 && D==cnt[3])continue; dp[ac[i].next[k]->index][state+bit[k]]=max(dp[ac[i].next[k]->index][state+bit[k]],dp[i][state]+ac[i].next[k]->isword); } } } } } } } int ans=0; int tag=cnt[0]*bit[0]+cnt[1]*bit[1]+cnt[2]*bit[2]+cnt[3]*bit[3]; for(int i=0;i
                
               
              
             
            
           
          
         
        
       
      
     

版权声明：本文博主原创文章。博客，未经同意不得转载。