Fukuoka 2011 F - City Merger

网友投稿 790 2022-10-20

Fukuoka 2011 F - City Merger <路径压缩,位运算,AC自动机>

Fukuoka 2011 F - City Merger

本题求用最短的长度字符串包含所给子串...由于存在多串匹配的问题...容易联想到AC自动机...

最多14个city..用14位的二进制数表示已经在串中否...对多串构造Trie树..进一步构造好AC自动机...可以用dp [ k ] [ i  ] [ x ] 来表示长度为k的串..末字符落在trie树的i处..包含14个关系的x...但这样的复杂度..以最坏的考虑..会有240*240*16384=943718400=9*10^8...无法接受...

那么此时就要压缩路径了..由于Trie树中有很多无法产生更新的点...没必要dp时一次又一次的路过...所以将Trie树中x非0的点找出来...从每个点开始BFS...做出到其他有效点的最短距离...这样大大优化了dp过程...

Program:

#include#include#include#include#include#include#include#include#define oo 1000000000using namespace std; struct node{ int fail,son[26],city,w;}point[1001]; struct node2{ int len,x;};int n,m,k,g,arc[303][303],need[303],l[303],dp[2][303][18000];char s[30]; queue myqueue;void Built_Trie(){ int len,i,j,k,h,x; memset(point,0,sizeof(point)); m=0; g=1; for (k=0;kdp[1-k][j][p]+arc[j][i]) dp[k][i][x]=dp[1-k][j][p]+arc[j][i]; } } ans=oo; for (i=0;i

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

标签：优化
上一篇:利用feign调用返回object类型转换成实体
下一篇:小程序打开APP（小程序打开app指定页面）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~