HDOJ-3427 & ZOJ-3190 Resource Archiver AC自动机压缩状态DP..

HDOJ-3427 & ZOJ-3190 Resource Archiver AC自动机压缩状态DP..

先用resources和virus构造出AC自动机..

resources..其中c是一个用十进制表示的二进制数..代表题目里最多10个resources的存在情况...可见此种dp..状态最多可为10000*60000*1024...爆空间爆时间..各种爆..爆得体无完肤!!..

根据sha崽的提示..本题AC自动机里虽然点很多..但实际在更新转移中存在意义的点只有包含了resources的后缀点..而这些点的个数只有不超过50个..so..将这些后缀点之间的最短路径算出来...我就是直接枚举每个点BFS的...然后直接对这些存在转移意义的后缀点DP..瞬间时间和空间爆降阿..

正如HDOJ本题Dicuss里有人说的..本题数据还是很弱的..我找了好多网上发布的AC代码...没有一个代码能够跑出完全正确的结果..错得最多的是Discuss里的:

3 3

0001

0000

10000

010

101

111

好不容易找到这个数据能过的..结果又一大堆没考虑resources相同的..还有一些连手算的简单数据都出错..这道题数据的不严谨.众AC代码漏洞百出.真是奇葩.

我WA了十多次的原因是因为..白痴了..一个赋初值的地方没注意到要清0..结果..WA得想吐..

Program：

#include#include#include#include#include#define oo 2000000000#define ll long longusing namespace std; struct node{ int son[2],fail,d,n; bool w;}point[60005];int n,m,_2jie[12],dis[55][55],dp[55][1026],useful[55];char s[50005];queue myqueue;int used[60005];int main(){ int len,i,j,x,h,k,num,ans,goal; _2jie[0]=1; for (i=1;i<=10;i++) _2jie[i]=_2jie[i-1]*2; while (~scanf("%d%d",&n,&m)) { if (!n && !m) break; memset(point,0,sizeof(point)); num=0; for (j=0;jdp[i][k]+dis[i][j]) dp[j][x]=dp[i][k]+dis[i][j]; } } ans=oo; for (i=1;i<=num;i++) if (dp[i][goal] && dp[i][goal]

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