当时是因为没有做出来这道题才开了自动机的专题，现在看看还是比较简单的。

因为每个病毒串只算一次，只有10个病毒串，可以状压一下哪些状态是可以达到的，最后取一个最大值。

1 #include 
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std; 12 #define N 1005 13 #define LL long long 14 #define INF 0xfffffff 15 const double eps = 1e-8; 16 const double pi = acos(-1.0); 17 const double inf = ~0u>>2; 18 const int child_num = 4; 19 char vir[115]; 20 int v[12]; 21 class AC 22 { 23 private: 24 int ch[N][child_num]; 25 int fail[N]; 26 int Q[N]; 27 int val[N]; 28 int sz; 29 int id[128]; 30 int dp[2][N][1<<10]; 31 char s[N]; 32 public: 33 void init() 34 { 35 fail[0] = 0; 36 id['A'] = 0,id['G'] = 1,id['T'] = 2,id['C'] = 3; 37 } 38 void reset() 39 { 40 memset(ch[0],0,sizeof(ch[0])); 41 memset(val,0,sizeof(val)); 42 sz = 1; 43 } 44 void insert(char *a,int key) 45 { 46 int p = 0; 47 for(; *a ; a++) 48 { 49 int d= id[*a]; 50 if(ch[p][d]==0) 51 { 52 memset(ch[sz],0,sizeof(ch[sz])); 53 s[sz] = *a; 54 ch[p][d] = sz++; 55 } 56 p = ch[p][d]; 57 } 58 val[p] = (1<
                
                 <= m ;i++)136 {137 scanf("%s%d",vir,&v[i-1]);138 ac.insert(vir,i-1);139 }140 ac.construct();141 ac.work(n,m);142 }143 return 0;144 }