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

题目链接

题解

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-jf[i][j]+=f[j][k]

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

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

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注