【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

 var map:array[..,..]of longint;

     q,a,size,fa:array[..]of longint;

     hash:array[..,..,..,..]of longint;

     dp:array[..,..]of longint;

     ch:string;

     n,cnt,i,j,k,x,t,y,ans,len,s,cas,a1,c1,g1,t1,u,s1,v,s2,num:longint;

     flag:boolean;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 function max(x,y:longint):longint;

 begin

  if x>y then exit(x);

  exit(y);

 end;

 procedure build;

 var i,u:longint;

 begin

  u:=;

  for i:= to len do

  begin

   if map[u,a[i]]= then

   begin

    inc(cnt); map[u,a[i]]:=cnt;

   end;

   u:=map[u,a[i]];

  end;

  inc(size[u]);

 end;

 procedure acauto;

 var t,w,i,p,son,u:longint;

 begin

  t:=; w:=; q[]:=;

  while t<w do

  begin

   inc(t); u:=q[t];

   size[u]:=size[u]+size[fa[u]];

   for i:= to  do

    if map[u,i]> then

    begin

     son:=map[u,i];

     p:=fa[u];

     if u= then fa[son]:=

      else fa[son]:=map[p,i];

     inc(w); q[w]:=son;

    end

     else

     begin

      p:=fa[u];

      if u= then map[u,i]:=

       else map[u,i]:=map[p,i];

     end;

  end;

 end;

 begin

  assign(input,'hdoj3341.in'); reset(input);

  assign(output,'hdoj3341.out'); rewrite(output);

  while not eof do

  begin

   readln(n);

   if n= then break;

   inc(cas);

   for i:= to cnt do

   begin

    size[i]:=; fa[i]:=;

   end;

   for i:= to cnt do

    for j:= to  do map[i,j]:=;

   for i:= to a1 do

    for j:= to c1 do

     for k:= to g1 do

      for x:= to t1 do hash[i,j,k,x]:=;

   cnt:=;

   for i:= to n do

   begin

    readln(ch);

    len:=length(ch);

    for j:= to len do

    begin

     case ch[j] of

      'A':a[j]:=;

      'C':a[j]:=;

      'G':a[j]:=;

      'T':a[j]:=;

     end;

    end;

    build;

   end;

   acauto;

   readln(ch);

   len:=length(ch); a1:=; c1:=; g1:=; t1:=;

   for i:= to len do

   begin

    case ch[i] of

     'A':inc(a1);

     'C':inc(c1);

     'G':inc(g1);

     'T':inc(t1);

    end;

   end;

   num:=;

   for i:= to a1 do

    for j:= to c1 do

     for k:= to g1 do

      for x:= to t1 do

      begin

       inc(num); hash[i,j,k,x]:=num;

      end;

  for i:= to cnt do

   for j:= to a1 do

    for k:= to c1 do

     for x:= to g1 do

      for y:= to t1 do dp[i,hash[j,k,x,y]]:=-;

   dp[,hash[,,,]]:=;

   ans:=;

   for i:= to a1 do

    for j:= to c1 do

     for k:= to g1 do

      for x:= to c1 do

      begin

       if i+j+k+x= then continue;

       s1:=hash[i,j,k,x];

       for u:= to cnt do

        for t:= to  do

        begin

         v:=map[u,t];

         s2:=;

         if (t=)and(i>=) then s2:=hash[i-,j,k,x]

         else if (t=)and(j>=) then s2:=hash[i,j-,k,x]

          else if (t=)and(k>=) then s2:=hash[i,j,k-,x]

           else  if (t=)and(x>=) then s2:=hash[i,j,k,x-];

         if s2= then continue;

         if dp[u,s2]=- then continue;

         dp[v,s1]:=max(dp[v,s1],dp[u,s2]+size[v]);

         ans:=max(ans,dp[v,s1]);

        end;

      end;

   writeln('Case ',cas,': ',ans);

  end;

  close(input);

  close(output);

 end.

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

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   610

 #define M   7010

 #define eps 1e-8

 #define pi  acos(-1)

 #define oo  1e9

 #define MOD 10007

 int nxt[N][],q[N],size[N],fa[N],num[][][][],dp[N][],

     A,C,G,T,len,cnt;

 char b[M],ch[M];

 void build()

 {

     int u=;

     for(int i=;i<=len;i++)

     {

         int t;

         if(b[i]=='A') t=;

         if(b[i]=='C') t=;

         if(b[i]=='G') t=;

         if(b[i]=='T') t=;

         if(!nxt[u][t]) nxt[u][t]=++cnt;

         u=nxt[u][t];

     }

     size[u]++;

 }

 void acauto()

 {

     int t=; int w=; q[]=;

     while(t<w)

     {

         int u=q[++t];

         size[u]+=size[fa[u]];

         for(int i=;i<=;i++)

         {

              if(nxt[u][i])

               {

                  int son=nxt[u][i];

                  int p=fa[u];

                  if(u==) fa[son]=;

                   else fa[son]=nxt[p][i];

                  q[++w]=son;

              }

               else

               {

                  int p=fa[u];

                  if(u==) nxt[u][i]=;

                   else nxt[u][i]=nxt[p][i];

               }

         }

     }

 }

 int main()

 {

     //freopen("hdoj3341.in","r",stdin);

     //freopen("hdoj3341.out","w",stdout);

     int n;

     int cas=;

     A=C=G=T=cnt=;

     while(scanf("%d",&n)!=EOF)

     {

         if(n==) break;

         cas++;

         for(int i=;i<=cnt;i++) size[i]=fa[i]=;

         for(int i=;i<=cnt;i++)

          for(int j=;j<=;j++) nxt[i][j]=;

         for(int i=;i<=A;i++)

          for(int j=;j<=C;j++)

           for(int k=;k<=G;k++)

            for(int x=;x<=T;x++) num[i][j][k][x]=;

         cnt=;

         for(int i=;i<=n;i++){scanf("%s",b+); len=strlen(b+); build();}

         acauto();

         scanf("%s",ch+);

         len=strlen(ch+);

         A=C=G=T=;

         for(int i=;i<=len;i++)

         {

             if(ch[i]=='A') A++;

             if(ch[i]=='C') C++;

             if(ch[i]=='G') G++;

             if(ch[i]=='T') T++;

         }

         int s=;

         for(int i=;i<=A;i++)

          for(int j=;j<=C;j++)

           for(int k=;k<=G;k++)

            for(int x=;x<=T;x++) num[i][j][k][x]=++s;

         for(int i=;i<=cnt;i++)

          for(int j=;j<=A;j++)

           for(int k=;k<=C;k++)

            for(int x=;x<=G;x++)

             for(int y=;y<=T;y++) dp[i][num[j][k][x][y]]=-;

         dp[][num[][][][]]=;

         int ans=;

         for(int i=;i<=A;i++)

          for(int j=;j<=C;j++)

           for(int k=;k<=G;k++)

            for(int x=;x<=T;x++)

            {

                     if(i+j+k+x==) continue;

                     int s1=num[i][j][k][x];

                     for(int u=;u<=cnt;u++)

                  for(int t=;t<=;t++)

                    {

                        int v=nxt[u][t];

                        int s2=;

                        if(t==&&i>=) s2=num[i-][j][k][x];

                        if(t==&&j>=) s2=num[i][j-][k][x];

                     if(t==&&k>=) s2=num[i][j][k-][x];

                     if(t==&&x>=) s2=num[i][j][k][x-];

                     if(s2==||dp[u][s2]==-) continue;

                     dp[v][s1]=max(dp[v][s1],dp[u][s2]+size[v]);

                     ans=max(ans,dp[v][s1]);

                  }

             }

         printf("Case %d: %d\n",cas,ans);

     }

     return ;

 }

巴特西

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

最新文章

热门文章