P5464 缩小社交圈——利用dp重叠的结构

li_cat · 2025-11-19 20:19:51 · 个人记录

考虑什么东西会影响方案的合法性

线段一定得铺成两层，所以需要记录最右和次右

于是就有了一个 n^3 的 dp

发现按右端点排序后， i 的维度就可以和最右合并了

发现应该进行一个一个的枚举而不是直接推到更久以前两个端点都不同的状态

两种转移

• 可以直接嵌套而不用考虑两个完全不同的状态拼接，即 i 带 j ， j 带 k ，考察这时 k 需要满足的要求
• 可以直接追溯自己的其它版本，即 i 带 j ， i 带 k ，试着能不能拼接

这个应该可以直接前缀和优化

应该学会充分利用重叠关系