题目列表

设 dp[i][j][s] 表示前 i 轮、已经换 j 次手势且当前手势为 s 时的最大胜场数。

设 dp[i][j][c] 表示走到第 i 行第 j 个位置且用了 c 次三倍经验时的最大得分，再按左右两个父节点转移。

设 dp[i][j] 表示前 i 分钟、移动 j 次后最多接到多少苹果，当前位置由 j 的奇偶唯一确定。

把食物网看成 DAG，令入度为 0 的点作为起点，按拓扑序递推每个点的路径条数。

把交替加法过程改写成 Fibonacci 型递推，再利用模 p 的周期在有限步内判断谁先变成 0。

按题目分支写递归函数，并用 lru_cache 记忆化 1 到 20 范围内的重复状态。

先用 Z 函数求每个位置和字典串前缀的最长匹配长度，再把这些匹配视作区间覆盖做最少跳数贪心。

按到达事件推进时间，维护当前运行进程和等待优先队列，遇到更高优先级进程时立即抢占。

按保质期从后往前安排每天吃什么，用小根堆维护当前仍可食用的最便宜巧克力。

按计算机分别维护当前运行任务的小根堆，先弹出已结束任务，再判断剩余算力是否足够。

每次合并当前最小的两堆果子，等价于构造 Huffman 树，用 Python 的 heapq 维护小根堆。

先预处理一段村庄只建一个邮局的代价，再做邮局数量分层 DP，并用决策单调性做分治优化。

把环断成长度为 n 的所有链段，做区间 DP，同时维护最小合并代价和最大合并代价。

把删点顺序转成树边定向，再做树形 DP，维护子树向根汇总权值与根向下可达点数的 Pareto 状态。

先用一元生成函数统计普通子树的剪枝顺序，再在 1 到 x 的路径上做带“前后分配”的树形计数 DP。

把装备合成关系看成森林，设 f[u][j][c] 表示在 u 的子树里留出 j 个 u 给父亲继续合成、花费 c 金币时能得到的最大力量值，再做树形分组背包合并子树。

把每张钞票看成独立物品，做 2 维 DP：dp[a][b] 表示最终分给 Alice 金额为 a、Bob 金额为 b 时最多能保留多少张原主人不变的钞票，答案是总张数减去最多保留张数。

做树上背包，设 f[u][j][sel][cov] 表示子树内选了 j 个点、u 是否放设备、u 是否被儿子监听的方案数，合并儿子时判断儿子是否能被父亲覆盖。

离散菜先做凹费用完全背包求每个整数重量的最优值，连续菜再把剩余重量写成分段二次函数最优分配，最后合并两部分答案。

先做一个容量 200 的 0/1 背包，求每个总 p 下能得到的最大总 k，再按回合数与 d 值差做极小极大动态规划。

先用完全背包预处理“花费 x 资源当秒最多新增多少采集效率”，再按时间推进 DP：dp[j] 表示当前手里有 j 资源时的最大已有采集效率。

把最多 5 种商品的购买数量压成 base-6 状态，把优惠包和单买都当成转移，在所有合法购买状态上做最短路式动态规划。

把每个任务的选择压成 A 机器总时间这一维，设 dp[x] 表示 A 用时为 x 时 B 的最小用时，最后在所有状态里取 max(A,B) 的最小值。

先把可行性化成“所选挂钩总数至少是所选挂饰数减一”，再把挂饰分成必选、必不选和可选三类，对负收益但能加挂钩的部分做 0/1 背包。

把第 i 个小矮人逃走前的条件整理成“已逃走肩高前缀不超过 T+a_i+b_i-H”，再按 a+b 排序并用大根堆维护最多可行人数。

把每个式子化成 `(#s-#c, #s+#c)`，再做差值背包，求总差值为 0 时总长度最大，答案就是长度的一半。

把分批完成的总费用用前缀和展开成线性形式后，对每个分界点建立直线，用单调队列做斜率优化 DP。

把连续分段费用写成前缀和形式后，展开平方得到标准斜率优化 DP，用单调队列维护下凸壳。

用前缀和写出连续分段的建仓代价后，把 DP 转移整理成关于位置 x 的直线最小值查询，并用单调队列做斜率优化。

先删除所有被支配矩形，把问题化成连续分段 DP，再用单调队列维护凸包优化转移。

把每个站点上的换乘 DP 写成关于发车时刻 p 的直线最小值查询，再按时间扫描并为每个站维护单调队列凸包。

把二维偏序上的最大收益路径 DP 拆成按列扫描，再用两层单调凸包分别处理历史列转移和当前列内的纵向转移。

把每个点看成按 x 坐标有向无环图上的一个状态，接收费用可整理成关于目标坐标 x 的直线，用 Li Chao Tree 维护左侧所有可转移点的最小值。

把家庭按最终去的会场分成 4 段，设 dp[k][i] 表示前 i 户用了 k 个中间会场的最小代价，再把区间代价整理成直线形式，用斜率优化把 3 层转移压到线性。

把每位同学的到达时刻平移为“最早可被接走的回程时刻”，再设 dp[x] 表示最后一班车在时刻 x 返回时的最小等待和，并用斜率优化维护转移直线。

用双指针枚举答案区间，再用单调队列维护当前窗口内“长度恰好为 d 的子段最大和”，从而快速判断把哪一段清零后能否让总和不超过 p。

设 dp[i] 表示到第 i 棵树的最少疲劳跳跃次数，用单调队列维护最近 k 棵树里“dp 更小且高度更优”的候选前驱，把每次询问做到 O(n)。

把每段固定方向的时间看成一次行或列上的区间转移，设 dp[x][y] 表示当前位置最大滑行距离，再用单调队列优化每段的滑动窗口最大值。

设 dp[i][j] 表示第 i 天结束时持有 j 股的最大收益，把买卖转移改写成区间最值，再用单调队列把每一天优化到 O(MaxP)。

先二分最长段长度的最小可行值，再在该上界下用滑动窗口优化的计数 DP 统计所有合法连续划分方案。

设 dp[i][j] 表示长度为 i、逆序对数为 j 的排列个数，再用插入最大值的转移和前缀和把求和优化到 O(nk)。

把每一行压成二进制状态，预处理单行合法状态后按行做状压 DP，统计所有不相邻的种草方案数。

先预处理单行合法状态，再按行做只依赖前两行的状压 DP，求最多能放多少炮兵。

枚举两只小猪反推出一条合法下凹抛物线，把每条抛物线离散成一个覆盖集合，再做最少集合覆盖的状压 DP。

把较短维压成二进制状态，按行做三行覆盖检查的轮廓 DP，并用 `(总代价, 油库数量)` 做字典序最优。

把每一列压成二进制状态，利用马只会影响前两列的性质，做记录前两列状态和已放马数量的轮廓 DP。

设 dp[mask][u] 为已经吃掉 mask 中这些奶酪且最后停在 u 的最短路程，做起点固定、终点不限的状压 TSP。

先在“单次飞行不超过 D”的图上跑 Floyd 求任意两村庄间最短可达代价，再在这个距离矩阵上做状压 TSP。

设 dp[mask] 为安排完这些牛后的最优状态，状态记录最少电梯趟数以及该趟数下最后一趟电梯的最小已载重量。

把每包糖果压成一个口味集合 mask，设 dp[mask] 为覆盖这些口味所需的最少包数，做集合覆盖型状压 DP。

把每份披萨看成一个原料子集，直接状压枚举所有 2^N 个子集并检查是否包含冲突对即可。

设 dp[u][0/1/2] 分别表示 u 放塔、被儿子覆盖、等父亲覆盖的最少塔数，用三状态树形 DP 求树上最小支配集。

把完全二叉树的不完整部分压缩成“最后一个叶子到根”的一条路径，预处理满树方案数后沿这条路径自底向上递推。

把路径内部点的贡献化成 deg(u)-1，将答案转成树上最大点权路径和，再在结尾补上两个端点贡献。

设 dp[u][j] 为 u 子树选 j 个黑点的最大收益，把同色点对距离和拆成每条边两侧黑点对与白点对数量乘边权的贡献来转移。

设 dp[u][j][0/1] 表示子树内选 j 个点给大头且 u 是否属于大头的最小代价，按 M=2 与 M>=3 分别判断父子边是否计入答案。

设 dp[u][j] 为在 u 子树中保留 j 条且仍能通过 u 连到根的边的最优收益，合并儿子时做树上分组背包。

先求以 1 为集会点时的总代价和各子树牛数，再用换根公式 dist[v]=dist[u]+(total-2*sub[v])*w 在线性时间求所有答案。

先用并查集缩掉所有 t=2 的相等点，再只保留 t=0 的不同色森林；计数是森林染色，最小和是带点权二分染色。

设 dp[u][c] 表示 u 染成颜色 c 时整棵子树的合法方案数，再把每个儿子所有不同色状态的方案数乘起来。