HDOJ-3341 好BT的AC自动机...T_T

好不容易空间卡时间过了...T_T.....

题意是给出N(<=50)个模式串(仅由ACGT构成的lengh=[1,10]的字符串)..给出目标串所包含的字符(同样只有ACGT..length=[1,40])..问通过所给字符组成的目标串中最多能包含多少个模式串...

用所有模式串构造AC自动机...

然后就DP吧...状态为dp[k][p]...代表AC自动机中点k..所构成'A'..'C'..'G'..'T'.个个数情况为p时所能得到的最多模式串...而这个状态表示方法最大的问题就是如和来表示p...最朴素的就是用[40][40][40][40]来表示'A'..'C'..'G'..'T'当前出现次数...题目所给最大内存为6M多..而存下所有状态要准备 500*40^4 内存显然爆了..那么就需要更好的方法来表示p..首先我们能发现虽然'A'..'C'..'G'...'T'..其中之一可能会到达40个..但是全部为40或者很多情况实际上不能出现...这样就开了很多跟本用不上的空间...

参考​​number of A ...of  C...of  G...of T and it's length)可以在做dp前打出来..那么在dp中这些信息就直接拿来用就是了..

2、一般的AC自动机dp..都是用滚动数组..以当前长度-1各点值来更新当前长度的各点值..而本题是不需要分两层滚动处理..因为这里是用dp[k][p]来存状态..而p本身就能体现出当前长度..(p包含了其length信息,事先就处理出来了..)

3、只有更新过的点才能更新其能达到的点(最初的0点外..)..为了满足这个要求..我开始用used[501][14642]来记录状态dp[k][p]是否有过更新..其实没必要...将dp[0][0]的初值赋值为1而不是0..而开始时其它的都是清0..那么在更新过程中..只要判断dp[k][p]是否为0就可知道其有无更新过...当然..最后得到的ans-1就是...

PS: 其实这题的测试数据弱了...我自己本地出了30组最大极限数据..程序跑13秒才出得来...囧...

Program:

#include#include#include#includeusing namespace std;struct node{ int son[4],w,fail;}point[501]; int dp[501][14642],st[14642][5],P[4];int n,num,T,ans,sum[4],i,j,x,y,l,len,h,k,m,A,B;queue myqueue;char s[41]; int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); while (!myqueue.empty()) myqueue.pop(); T=0; while (~scanf("%d\n",&n)) { if (!n) break; memset(point,0,sizeof(point)); num=0; while (n--) { gets(s); len=strlen(s); h=0; for (i=0;ians) ans=dp[i][x]; ans--; printf("Case %d: %d\n",++T,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。