关于nlogn求LCS

水星湖 @ 2024-06-09 00:07:16

by 红黑树 @ 2024-06-09 00:47:23

直接线段树或者树状数组优化 DP 就行了吧，LCS 不是只能转 LIS 做的。

by 红黑树 @ 2024-06-09 00:48:28

你们可以看看这篇题解，可以暴力维护 DP 的。

https://www.luogu.com.cn/article/6wpfgap0

by hdkk @ 2024-06-09 00:50:12

@红黑树 但是有重复的话决策点数量是 n^2 级别的

by hdkk @ 2024-06-09 00:51:01

@红黑树 还是不可做不是吗/yun

by 红黑树 @ 2024-06-09 00:52:09

他本来就是 n^2 的啊，跟你重复不重复有啥关系吗？

by hdkk @ 2024-06-09 00:52:40

@红黑树 ee，如果是排列的话就是 n 个啊

by 红黑树 @ 2024-06-09 00:53:31

不是，你有多个可选点的话肯定会选能选的里面最靠前的那个啊

by 红黑树 @ 2024-06-09 00:53:49

所以是不是不影响

by hdkk @ 2024-06-09 00:54:29

@红黑树 艹好像有道理，我想想

by hdkk @ 2024-06-09 00:57:26

@红黑树 感觉还是不对啊，决策点是二维的，你要是说有两个决策点不满足二维偏序，你怎么知道哪个更优