Page 5 - Showing 15 of 134 posts
- D21 树的重心
树的重心：删去后最大子树最小。
3 min read zh - D22 Kruscal重构树
Kruscal 重构树：最小瓶颈 / 连通性离线问题。
4 min read zh - D23 2-SAT
2-SAT：变量拆点 + Tarjan 强连通判定与构造。
4 min read zh - D24 2-SAT-前缀优化建图
2-SAT 前缀优化建图：每部分恰选一个 + 边至少一端选。
5 min read zh - E1 最长上升子序列（二分优化）
LIS 最长上升子序列：二分 + 贪心 O(n log n)。
2 min read zh - E2 最长公共子序列
LCS 最长公共子序列：二维 DP。
3 min read zh - E3 最长公共子串
最长公共子串：DP / 后缀自动机。
2 min read zh - E4 01背包
01 背包：每件物品选或不选，滚动数组优化。
2 min read zh - E5 完全背包
完全背包：物品可无限选取，正序递推。
2 min read zh - E6 多重背包
多重背包：物品有数量限制（二进制拆分）。
3 min read zh - E7 滑动窗口
滑动窗口：双端队列（单调队列）维护区间最值。
4 min read zh - E8 混合背包
混合背包：01 / 完全 / 多重背包组合。
3 min read zh - E9 二维背包
二维费用背包：体积与重量两个限制。
2 min read zh - E10 分组背包
分组背包：每组最多选一个。
2 min read zh - E11 树形DP
树形 DP：以子树为状态的树上动态规划。
4 min read zh