「Codechef」STREDUC-DP

发布于 26 天前  80 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codechef」STREDUC-DP

Description

给定一个字符串 $s$ 和一个字符串集合,每次操作是在$s$中找到一个在字符串集合出现过的子串,然后删去这个子串。剩下的串会拼在一起。

求删去后的最短串 $s$。

Solution

首先为了方便,将给定的字符串集合构一棵$Trie$树。

设 $f_{i,j,k}$ 表示下标为 $[i,j]$ 的子串,目前未被删去的部分在字典树上的节点为 $k$, $w_{i,j}$表示下标为 $[i,j]$ 的子串是否能被消掉。

有两种转移。

$$f_{i,j,k}=f_{i,l-1,k} | (w[l][j]=true)$$

$$f_{i,j,ch[k][c]}=f_{i,j-1,k}$$

第一种转移表示消去$w[l][j]$的一段,第二种转移表示不消去任何子串,添加一个字符。

当$k$代表一个字符串集合中的串时,$w_{i,j}=true$

最后写一个$O(n^2)$的DP即可。

p.s: 由于第一种转移复杂度较高,要用bitset优化。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codechef」STREDUC-DP


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!