POJ-1625 & ZOJ-1540 & Ural-1158 AC自动机+DP+大数..

POJ-1625 & ZOJ-1540 & Ural-1158 AC自动机+DP+大数..

AC自动机的DP...每个节点是状态..每条边是转移方向..其实这题和 POJ-2778 DNA Sequence  是一回事..只是这题是高精度..并且数据范围没那么大..所以使得直接DP的效率从时间和空间上都远远高于了用矩阵乘法...囧..

其实准确的说这题所构造的图不是AC自动机而是Trie图...为了DP转移时更加方便..把节点没有的孩子赋值为其fail点的这个孩子...这样在DP时就不用考虑fail了..直接枚举每个点来通过这个点的有向边更新其他点...

DP时很明显每一次都只于前一次有关...所以可以用滚动数组来存点的dp值..

DP转移方程为:

v[k][x]+=v[1-k][h];      (k做滚动数组标记的..h是有向线段的起点..x是有向线段的终点)

这题很显然要用高精度了..因为是这样的转移关系..所以只要考虑在做加法的时候会不会爆..我是每位存8个十进制数...效率确实很好....

这题非常要小心的一个是对带病毒点的处理...还有就是对结果是0的处理...我就是处理得不彻底结果WA了N久....

我的一些测试数据(也贴在POJ-1625的Discuss了..):

50 50 10 qwertyuiop[]\asdfghjkl;'zxcvbnm,./ QWERTYUIOP{}|AS aegaegu etoijqt tquqi witowwt zxcjnc oeit potieq iojge nvoq piqper ans=8881647922834867244791415981705771412427494861672253136057167374729235842468240763290 1 1 1 a a ans=0 5 10 3 abcde abc bc c

ans=1048576

Program:

#include#include#include#include #define uchar unsigned char#define N 55using namespace std;struct node1{ int son[55],fail; bool w;}point[202]; int n,m,p,v[2][202][N+2],g[606];char s[105];bool used[202];queue myqueue; int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,l,a[N+2],num,h,k; scanf("%d%d%d\n",&n,&m,&p); gets(s); l=strlen(s); memset(g,0,sizeof(g)); for (i=0;i99999999) { v[k][point[h].son[i]][p+1]+=v[k][point[h].son[i]][p]/100000000; v[k][point[h].son[i]][p]%=100000000; } } } } } memset(a,0,sizeof(a)); for (i=0;i<=num;i++) for (p=0;p99999999) { a[p+1]+=a[p]/100000000; a[p]%=100000000; } } for (p=N;p>=0;p--) if (a[p]) break; if (p==-1) p=0; printf("%d",a[p]); p--; for (;p>=0;p--) { if (a[p]<10000000 ) printf("0"); if (a[p]<1000000 ) printf("0"); if (a[p]<100000 ) printf("0"); if (a[p]<10000 ) printf("0"); if (a[p]<1000 ) printf("0"); if (a[p]<100 ) printf("0"); if (a[p]<10 ) printf("0"); printf("%d",a[p]); } printf("\n"); return 0;}

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