[CF611D]New Year and Ancient Prophecy(动态规划)

发布于 2019-04-06  63 次阅读


题目链接

题解

$f[i][j]$ 表示 当前串为第j个位置到第i个位置的串的方案数

$O(n^3)$ 做法
$ f[i][j]=\sum_{j-k< i-j}f[j][k]$

若 $s(k+1,j)< s(j+1,i),j-k=i-j$ 则 $f[i][j]+=f[j][k]$

$O(n^2)$ 做法
考虑 $O(1)$ check $s(k+1,j)<s(j+1,i)$

逗逼神仙做法:SA
简单做法:求 $lcp(I,j)$ 即$s[i],s[j]$ 的最长公共前缀
若 $lcp(k,j)<j-k-1 $ 并且 $s[k+ lcp(k,j)+1]< s[j+ lcp(k,j)+1]$ 则合法

代码


哇,你居然发现了这里!