专栏文章

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

2025/11/19 20:19个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论: 0 条
当前快照: 1 份
快照标识符: @min4qhwu
此快照首次捕获于: 2025/12/01 20:32
此快照最后确认于: 2025/12/01 20:32

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

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

于是就有了一个

n^3

的

dp

发现按右端点排序后，

i

的维度就可以和最右合并了

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

两种转移

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

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

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...