国庆集训 Day 1~2 笔记 - 动态规划
DP 时间复杂度计算：状态数 $\times$ 决策数 $\times$ 转移代价
序列型 DP
最长上升子序列
B3637 最长上升子序列 - 洛谷
- $O(n^2)$ 解法：$f_i = \max{f_j + 1}$，其中 $a_j < a_i$
- $O(n \log n)$ 解法：二分优化转移或树状数组
划分型 DP
一般状态：$f_{i,j}$ 表示前 $i$ 个数分 $j$ 组
数的划分
[P1025 NOIP2001 提高组] 数的划分 - 洛谷
题目：将 $N$ 分为 $K$ 个数，不考虑顺序（即 $1,2,1$ 与 $1,1,2$ 为同一种情况）
- $f_{i,k,x}$ 表示 $i$ 分为 $k$ 个数，其中最大值为 $x$
- $f_{i,k,x} += f_{i-x,k-1,y}$，其中 $y \in [1,x]$
- 答案：$\text{ans} = \sum_{x=1}^N f_{N,K,x}$
优化（优化状态）：考虑 $1$ 的存在
- $f_{i,k} = f_{i-1,k-1} + f_{i-k,k}$
另解：DFS
抄书问题
P1281 书的复制 - 洛谷
P1182 数列分段 Section II - 洛谷
[P2884 USACO07MAR] Monthly Expense S - 洛谷
题目：$n$ 个数分为 $K$ 组，使各组的和的最大值最小
- $f_{i,j}$ 表示前 $i$ 个分 $j$ 组的最小最大值
- $s_i$ 为前缀和
- 枚举上一段末尾 $k$：$f_{i,j} = \min{\max(f_{k,j-1}, s_i - s_k)}$
优化：
- 转化 for 循环顺序：最外层枚举 $j$，中间枚举 $i$，最内层枚举 $k$
- 可降维为 $f_i$
另解：数据较大且不要求输出方案时，可使用二分答案
棋盘型 DP
（内容待补充）
区间 DP
一般状态：$f_{l,r}$ 表示一个区间
区间顺序：区间长度从小到大，左端点从小到大
状态转移：
- 扩展（左右两个方向）
- 合并（枚举断点）
石子合并
[P1880 NOI1995] 石子合并 - 洛谷
- $f_{l,r}$ 表示合并完 $[l,r]$ 得到的最大分数
- 枚举断点 $k$，其中 $k \in [l,r)$
- $f_{l,r} = \max(f_{l,k} + f_{k+1,r}) + s_r - s_{l-1}$
对于环状问题：可拓展 2 倍，转换为链后 DP（本质是枚举起点）