冒泡ioa
冒泡ioa

[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)<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] 则合法

代码

发表评论

textsms
account_circle
email

冒泡ioa

[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-j$ 则 $f[i][j]+=…
扫描二维码继续阅读
2019-04-06