【HDOJ3341】Lost's revenge（AC自动机，DP）

题意：给出一个n个模式串，一个目标串，问把目标串重新排位最多能产生多少个模式串，可以重叠且所有串只包含A C G T。

n<=10,len[i]<=10

len(s)<=40

Cas<=30

思路：TLE，估计被卡常了

可以将题意理解为重新构造一个ACGT个数都与原目标串相同的新串，则目标串中有用的信息只有ACGT个数

建出Trie图，跑一遍AC自动机，再用一个二维dp[i,j]表示trie上i号节点，字母使用情况为j的模式串最多出现次数

其中j为状态压缩量，是一个四维的量压成一维，因为不压的话会MLE

dp[v,h(a,b,c,d)]=max(dp[v,h(a,b,c,d)],dp[u,h(a-1,b,c,d)]+size[v])等四种转移

其中v=map[u,i]，size[v]表示trie上到v节点路径出现次数之和

边界条件dp[1,h(0,0,0,0)]=1

  1 var map:array[1..600,1..4]of longint;
  2     q,a,size,fa:array[0..16000]of longint;
  3     hash:array[0..40,0..40,0..40,0..40]of longint;
  4     dp:array[0..600,0..16000]of longint;
  5     ch:string;
  6     n,cnt,i,j,k,x,t,y,ans,len,s,cas,a1,c1,g1,t1,u,s1,v,s2,num:longint;
  7     flag:boolean;
  8 
  9 function min(x,y:longint):longint;
 10 begin
 11  if x<y then exit(x);
 12  exit(y);
 13 end;
 14 
 15 function max(x,y:longint):longint;
 16 begin
 17  if x>y then exit(x);
 18  exit(y);
 19 end;
 20 
 21 procedure build;
 22 var i,u:longint;
 23 begin
 24  u:=1;
 25  for i:=1 to len do
 26  begin
 27   if map[u,a[i]]=0 then
 28   begin
 29    inc(cnt); map[u,a[i]]:=cnt;
 30   end;
 31   u:=map[u,a[i]];
 32  end;
 33  inc(size[u]);
 34 end;
 35 
 36 procedure acauto;
 37 var t,w,i,p,son,u:longint;
 38 begin
 39  t:=0; w:=1; q[1]:=1;
 40  while t<w do
 41  begin
 42   inc(t); u:=q[t];
 43   size[u]:=size[u]+size[fa[u]];
 44   for i:=1 to 4 do
 45    if map[u,i]>0 then
 46    begin
 47     son:=map[u,i];
 48     p:=fa[u];
 49     if u=1 then fa[son]:=1
 50      else fa[son]:=map[p,i];
 51     inc(w); q[w]:=son;
 52    end
 53     else
 54     begin
 55      p:=fa[u];
 56      if u=1 then map[u,i]:=1
 57       else map[u,i]:=map[p,i];
 58     end;
 59  end;
 60 end;
 61 
 62 begin
 63  assign(input,'hdoj3341.in'); reset(input);
 64  assign(output,'hdoj3341.out'); rewrite(output);
 65  while not eof do
 66  begin
 67   readln(n);
 68   if n=0 then break;
 69   inc(cas);
 70   for i:=1 to cnt do
 71   begin
 72    size[i]:=0; fa[i]:=0;
 73   end;
 74   for i:=1 to cnt do
 75    for j:=1 to 4 do map[i,j]:=0;
 76   for i:=0 to a1 do
 77    for j:=0 to c1 do
 78     for k:=0 to g1 do
 79      for x:=0 to t1 do hash[i,j,k,x]:=0;
 80 
 81   cnt:=1;
 82   for i:=1 to n do
 83   begin
 84    readln(ch);
 85    len:=length(ch);
 86    for j:=1 to len do
 87    begin
 88     case ch[j] of
 89      'A':a[j]:=1;
 90      'C':a[j]:=2;
 91      'G':a[j]:=3;
 92      'T':a[j]:=4;
 93     end;
 94    end;
 95    build;
 96   end;
 97   acauto;
 98   readln(ch);
 99   len:=length(ch); a1:=0; c1:=0; g1:=0; t1:=0;
100   for i:=1 to len do
101   begin
102    case ch[i] of
103     'A':inc(a1);
104     'C':inc(c1);
105     'G':inc(g1);
106     'T':inc(t1);
107    end;
108   end;
109   num:=0;
110   for i:=0 to a1 do
111    for j:=0 to c1 do
112     for k:=0 to g1 do
113      for x:=0 to t1 do
114      begin
115       inc(num); hash[i,j,k,x]:=num;
116      end;
117 
118  for i:=1 to cnt do
119   for j:=0 to a1 do
120    for k:=0 to c1 do
121     for x:=0 to g1 do
122      for y:=0 to t1 do dp[i,hash[j,k,x,y]]:=-1;
123   dp[1,hash[0,0,0,0]]:=0;
124 
125   ans:=0;
126   for i:=0 to a1 do
127    for j:=0 to c1 do
128     for k:=0 to g1 do
129      for x:=0 to c1 do
130      begin
131       if i+j+k+x=0 then continue;
132       s1:=hash[i,j,k,x];
133       for u:=1 to cnt do
134        for t:=1 to 4 do
135        begin
136         v:=map[u,t];
137         s2:=0;
138         if (t=1)and(i>=1) then s2:=hash[i-1,j,k,x]
139         else if (t=2)and(j>=1) then s2:=hash[i,j-1,k,x]
140          else if (t=3)and(k>=1) then s2:=hash[i,j,k-1,x]
141           else  if (t=4)and(x>=1) then s2:=hash[i,j,k,x-1];
142         if s2=0 then continue;
143         if dp[u,s2]=-1 then continue;
144         dp[v,s1]:=max(dp[v,s1],dp[u,s2]+size[v]);
145         ans:=max(ans,dp[v,s1]);
146        end;
147      end;
148   writeln('Case ',cas,': ',ans);
149  end;
150  close(input);
151  close(output);
152 end.

UPD（2018.10.27）：C++重写果然C++常数小

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<string>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<algorithm>
  7 #include<map>
  8 #include<set>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef unsigned int uint;
 14 typedef unsigned long long ull;
 15 typedef pair<int,int> PII;
 16 typedef vector<int> VI;
 17 #define fi first
 18 #define se second
 19 #define MP make_pair
 20 #define N   610
 21 #define M   7010
 22 #define eps 1e-8
 23 #define pi  acos(-1)
 24 #define oo  1e9
 25 #define MOD 10007
 26 
 27 int nxt[N][4],q[N],size[N],fa[N],num[41][41][41][41],dp[N][16010],
 28     A,C,G,T,len,cnt;
 29 char b[M],ch[M];
 30 
 31 void build()
 32 {
 33     int u=1;
 34     for(int i=1;i<=len;i++)
 35     {
 36         int t;
 37         if(b[i]=='A') t=0;
 38         if(b[i]=='C') t=1;
 39         if(b[i]=='G') t=2;
 40         if(b[i]=='T') t=3;
 41         if(!nxt[u][t]) nxt[u][t]=++cnt;
 42         u=nxt[u][t];
 43     }
 44     size[u]++;
 45 }
 46             
 47 void acauto()
 48 {
 49     int t=0; int w=1; q[1]=1;
 50     while(t<w)
 51     {
 52         int u=q[++t];
 53         size[u]+=size[fa[u]];
 54         for(int i=0;i<=3;i++)
 55         {
 56              if(nxt[u][i])
 57               {
 58                  int son=nxt[u][i];        
 59                  int p=fa[u];
 60                  if(u==1) fa[son]=1;
 61                   else fa[son]=nxt[p][i];
 62                  q[++w]=son;
 63              }
 64               else
 65               {
 66                  int p=fa[u];
 67                  if(u==1) nxt[u][i]=1;
 68                   else nxt[u][i]=nxt[p][i];
 69               }
 70         }
 71     }
 72 }
 73 
 74 
 75 
 76 int main()
 77 {
 78     //freopen("hdoj3341.in","r",stdin);
 79     //freopen("hdoj3341.out","w",stdout);
 80     int n;
 81     int cas=0;
 82     A=C=G=T=cnt=0;
 83     while(scanf("%d",&n)!=EOF) 
 84     {
 85         if(n==0) break;
 86         cas++;
 87         for(int i=1;i<=cnt;i++) size[i]=fa[i]=0;
 88         for(int i=1;i<=cnt;i++)
 89          for(int j=0;j<=3;j++) nxt[i][j]=0;
 90         for(int i=0;i<=A;i++)
 91          for(int j=0;j<=C;j++)
 92           for(int k=0;k<=G;k++)
 93            for(int x=0;x<=T;x++) num[i][j][k][x]=0; 
 94         cnt=1;
 95         for(int i=1;i<=n;i++){scanf("%s",b+1); len=strlen(b+1); build();}
 96         acauto();
 97         scanf("%s",ch+1);
 98         len=strlen(ch+1);
 99         A=C=G=T=0;
100         for(int i=1;i<=len;i++)
101         {
102             if(ch[i]=='A') A++;
103             if(ch[i]=='C') C++;
104             if(ch[i]=='G') G++;
105             if(ch[i]=='T') T++;
106         }
107         int s=0;
108         for(int i=0;i<=A;i++)
109          for(int j=0;j<=C;j++)
110           for(int k=0;k<=G;k++)
111            for(int x=0;x<=T;x++) num[i][j][k][x]=++s;
112         for(int i=1;i<=cnt;i++)
113          for(int j=0;j<=A;j++)
114           for(int k=0;k<=C;k++)
115            for(int x=0;x<=G;x++)
116             for(int y=0;y<=T;y++) dp[i][num[j][k][x][y]]=-1;
117         dp[1][num[0][0][0][0]]=0;   
118         int ans=0;
119         for(int i=0;i<=A;i++)
120          for(int j=0;j<=C;j++)
121           for(int k=0;k<=G;k++)
122            for(int x=0;x<=T;x++)
123            {
124                     if(i+j+k+x==0) continue;
125                     int s1=num[i][j][k][x];
126                     for(int u=1;u<=cnt;u++)
127                  for(int t=0;t<=3;t++)
128                    {
129                        int v=nxt[u][t];
130                        int s2=0;
131                        if(t==0&&i>=1) s2=num[i-1][j][k][x];
132                        if(t==1&&j>=1) s2=num[i][j-1][k][x];
133                     if(t==2&&k>=1) s2=num[i][j][k-1][x];
134                     if(t==3&&x>=1) s2=num[i][j][k][x-1];
135                     if(s2==0||dp[u][s2]==-1) continue;
136                     dp[v][s1]=max(dp[v][s1],dp[u][s2]+size[v]);
137                     ans=max(ans,dp[v][s1]);
138                  }
139             }
140         printf("Case %d: %d
",cas,ans);   
141     }
142     return 0;
143 }
144     
145