Luogu 4290 – 「HAOI2008」玩具取名

题目链接:Luogu 4290

区间DP,设计状态$f(l,r,c)$表示子串$s[l \cdots r]$ 能否由$c$扩展得到。如果区间长度为1,即$l = r$,那么$f(l,r,c)$的值代表这个位置的字符和$c$是否相等,如果相等则为1。题目中给出了$c$可以扩展成哪两个字符$c_x$和$c_y$,那么对于长度大于1的区间,即$l < r$,考虑是否存在$l \leq k < r$,使得区间$[l, k]$可以由$c_x$扩展得到,区间$[k+1, r]$可以由$c_y$扩展得到,那么

$$f(l,r,c) =\bigcup_{l \leq k < r} [ f(l, k, c_x) \cap f(k+1,r, c_y)  ]$$

我们需要对每个$c$,枚举$c_x$和$c_y$,对于每组$(c_x,c_y)$,枚举$l \leq k < r$,汇总得到$f(l,r,c)$的值。

后记:可能常数比较大?洛谷开O2过的。不管了反正现在是ICPC全开O2。

 

 

说点什么

avatar
50
  Subscribe  
提醒