动态规划从精通到入门

前言

本文将在笔者退役前持续更新，可能会有大量例题。

经典设计

[UOI 2024]Heroes and Monsters

1. \(dp(i,j)\) 表示考虑到第 \(i\) 选了 \(j\) 个的方案数。
2. 将问题转化为固定转移方案可以使用多项式级别的动态规划

[HAOI2015] 树上染色
树上问题，路径问题考虑边的转移次数，解决后效性。

[ABC416f]Paint Tree 2
逐个考虑，状态 \(0/1\) 表示是否可以继续转移。

经典优化

对于互不相关的两位状态 \(t_1,t_2\)，可以先转移 \(t_1\)，再转移 \(t_2\)。

优化转移

link
不难想到当有 \(k\) 个成功和 \(n-k\) 个失败时，每一边最优方案为排序后两两配对。
考虑枚举 \(k\)，记 \(dp(i,j)\) 表示考虑到前 \(i\) 个 \(j\) 个成功的方案数，容易转移，复杂度 \(O(n^3)\)。
考虑优化转移，对于每个 \(k\) 找到一个转移点，将两边分别考虑选几个 \(O(n)\) 转移。
我们发现满足一个在 \(a\) 序列上找到左侧都小于 \(b_k\) 右侧都大于 \(b_k\) 的转移点即可满足条件。
前缀和输出即可，复杂度 \(O(n^2)\)。