分类： CF

vp了这一场，这个D题难到出现断层。。。C过了1k人的时候D没人过，太狠了

主要是能想到用dp搞字符串匹配的。。。div2里这样的人应该不多吧

但是这个题其实内涵里有诱导dp的思想：刚开始没有搞懂他这里的append是什么意思，后来才懂得他每次的+-操作都是在修改对应的religion的描述，这个描述是一个只有小写字母的先后顺序固定的字符串。。然后题目问的就是给定你一个字符串叫做word of universe，问3个religion能不能共存，其实意思就是能不能从这个word of universe分离出来三个subsequence，他们互不相交，又正好是3个religion的描述。

vp的时候毫无头绪，正解里的预处理表倒是想到了也写了但是没用上。确实没想到会是dp emmmm 。既然dp那一定有个数值型的对象吧，他这里就很妙的把问题转化为满足这三个subsequence共存的序列至少要多长了。。。当然给定的word of universe是确定的，这里其实可以认为后面还有无限长的字符串。。。但是长度大于n的时候我们认为没用了。。就输出NO就可以。不得不说确实是很精妙，legendary出的题确实厉害👍

具体地，设dp(n1,n2,n3)为region1满足前n1个字符，region2满足前n2个，region3满足前n3个这样的情况下所需要的在word of universe里的前缀至少有多长。有一个暴力的计算O(250^3)复杂度的，就是

\[
dp\left(n_{1}, n_{2}, n_{3}\right)=\min \left\{\begin{array}{ll}{Nst\left(dp\left(n_{1}-1, n_{2}, n_{3}\right)+1, \text{description}_{1}\left[n_{1}\right]\right)} & {\text { if } n_{1} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}-1, n_{3}\right)+1, \text{description}_{2}\left[n_{2}\right]\right)} & {\text { if } n_{2} \geq 1} \\ {Nst\left(dp\left(n_{1}, n_{2}, n_{3}-1\right)+1, \text { description }_{3}\left[n_{3}\right]\right)} & {\text { if } n_{3} \geq 1}\end{array}\right.
\]

继续阅读“[DP][字符串匹配][子序列] codeforces 1150 D Three Religions”