Algorithm - DP

0. 前言

关于 DP 我很早就想做总结性的东西。寒假要提前放假了，那么，加油吧！

1. “基础 DP”

看似简单的算法，却能把你难死

1.1 区间 DP

1.2 树形 DP

1.3 基环树 DP

1.4 其他 DP

2. DP 的优化/突破

2.1 性质的优化/突破

1. CF1209E2

首先我们需要冲破这个圈子：每行取最大，太难了！干脆让 DP 去取最大。

考虑每列给答案贡献一个子集。每一列的预处理很方便也很快。

但是这个复杂度还是寄了。

仔细思考，会发现只会选择最大值排前 \(n\) 的几列。为啥？

然后随手 DP 了。 code

2.1 算法的优化

2.1.0 不能再简单的单调队列优化

2.1.1 斜率优化

2.1.2 决策单调性优化