博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU2825 Wireless Password [AC自动机+压缩DP]
阅读量:7221 次
发布时间:2019-06-29

本文共 1061 字,大约阅读时间需要 3 分钟。

  给出M个单词,问长度为N的包含不少于K个单词的字符串一共有多少个。到目前为止做的自动机的题目好像都是差不多样子。。都是包含不包含单词之类的。。

  这题用d[i][j][k]表示第i步走到字符j包含了单词集合k,因为一共只有10个单词,可以用二进制压缩状态表示这个集合。注意在建立trie图时要合并节点和它的fail节点的状态,一开始没想到这个WA了一次。状态转移方程为

  

  不加优化的代码交上去时间接近TLE。。。于是改成了滚动数组,并用for循环清0,还是要跑360ms左右。这相对于1s的时限还是很慢的。。。于是点了下Statistic,发现大家都是跑了好几百ms。。。。

#include 
#include
#define MAXN 105#define ALP 26#define MOD 20090717int n,m,k;char s[11];int next[MAXN][ALP],fail[MAXN],flag[MAXN],pos;int newnode(){ for(int i=0;i
=MOD)x%=MOD; } } } } //统计第n步走过>=k个单词的状态的总数 int ans=0; for(int s=0;s
=MOD)ans%=MOD; } } return ans;}int main(){ //freopen("test.in","r",stdin); while(scanf("%d%d%d",&n,&m,&k),n||m||k){ pos=0;newnode(); for(int i=1;i<=m;i++){ scanf("%s",s); insert(s,i); } makenext(); int ans=dp(); printf("%d\n",ans); } return 0;}

 

  

转载于:https://www.cnblogs.com/swm8023/archive/2012/08/07/2626535.html

你可能感兴趣的文章
如何培养良好的编程风格
查看>>
Go channel 实现归并排序中的 merge 函数
查看>>
Handler消息机制
查看>>
Dart4Flutter - 不可变性
查看>>
Android OkHttp简易使用
查看>>
Netty Channel源码分析
查看>>
设计模式学习之生成器模式
查看>>
初来乍到
查看>>
(二)构建dubbo分布式平台-平台功能导图
查看>>
promise原理就是这么简单
查看>>
用canvas实现一个colorpicker
查看>>
进击的 JavaScript(四) 之 闭包
查看>>
基于 HTML5 WebGL 的 3D 机房
查看>>
前端CORS请求梳理
查看>>
第八周Swift总结
查看>>
Java枚举比较用equals还是==
查看>>
Java编程——数据库两大神器:索引和锁
查看>>
SpringBoot整合Swagger2
查看>>
ImageLoader的优化写法
查看>>
谈项目中如何选择框架和库(FEDAY主题分享总结)
查看>>