题目列表

两个 100 位十进制数相乘远超 64 位整型，需用高精度乘法：把每位拆出来做竖式双重循环累乘，再从低位到高位进位即可。

方案是多重集合，用非递增序列作代表元去掉排列重复；按末位是否为 0 得到 f(M,N)=f(M,N-1)+f(M-N,N)，记忆化后 O(MN)。

把两笔交易用拆分点 i 解耦成前缀单笔最优 f(i) + 后缀单笔最优 g(i)，正反两遍扫描维护窗口最值，O(N) 取最大值。

扔鸡蛋问题：f[i][j] 为 i 层楼、j 个蛋最坏情况的最少扔蛋次数，枚举首扔位置 x，碎则测下层段且蛋减一、不碎测上层段蛋不变，max 套 min，预计算全表后每组询问 O(1) 查表。

线性 DP：f[i] 表示前 i 家店铺的最大收益，每家店铺选或不选，转移时保证相邻两家不同时选。

LCS 二维前缀 DP，两行滚动数组压缩空间，内层只扫较短串。

编辑距离 DP：用 dp[j] 滚动数组记录把 a 前缀变成 b 前缀的最少操作次数。

每只小精灵都是价值为 1 的物品，用精灵球数与皮卡丘体力（预算 M-1）作二维费用做 0/1 背包，再读单调整行得到最小体力消耗。

一维 0-1 背包 DP：倒序枚举容量，保证每件物品至多选一次，O(nm) 求出不超过背包容量的最大价值。

完全背包计数：f[j] 表示凑成 j 元方案数，f[0]=1，按 10/20/50/100 正序滚动 f[j]+=f[j-price]；n=0 输出 0。

体积既当重量又当收益的 0/1 背包：dp[s] 表示体积 s 能否被拼出，从大到小刷一遍，最后从 V 往下找最大可达体积，V 减去它即最小剩余空间。

0/1 背包计数：ways[0]=1，ways[s] += ways[s-a[i]] 且容量倒序枚举，答案即 ways[t]，O(nt)。

以每个地点作为最后一家店做线性 DP，转移时取满足距离大于 k 的前驱中最优的利润，答案取所有收尾位置的最大值。

按结尾位置合并子问题：f[i] 记录以 h[i] 结尾的最长不增子序列长度，转移在前面不低于 h[i] 的位置里取最大，O(n²) 后对全体取最大。

数字三角形经典 DP：自底向上滚动数组，O(h²) 时间求最大路径和。

网格只能向东、向南走，到达每格的最大收获只由上方与左方两格决定，线性 DP 一维滚动数组 O(RC) 直接推进到东南角。

DP：f[i] 表示以 a[i] 结尾的最大上升子序列和，从前驱严格更小的位置转移，最后取全部 f[i] 的最大值。

时限 2N-1 恰等于右下路径的格子数，路径只能向右或向下，退化为经典二维网格 DP，滚动数组 O(N^2) 求最小费用。

把“上一束花落在哪个花瓶”压成前缀最大值 g[i][t]，用 O(FV) 线性 DP 求最大美学值，再逐层取最靠左的最优落点回溯出严格递增的摆放方案。

按峰顶拆分：以每个景点为峰，正反各做一次 O(n^2) 的最长严格上升子序列 DP，ups[i]+downs[i]-1 的最大值即最多浏览景点数。

把格子按高度升序作为拓扑序，迭代填表求最长严格递减路径。

按长度归类维护最小结尾数组 tails，用二分查找把朴素 O(N²) DP 优化为每元素一次定位的 O(N log N) 贪心扫描。

把长度为 N 的数字串插入 K 个乘号切成 K+1 段使乘积最大。

末位三选一的前缀 DP：相同取对角线，不同取删除/插入/替换三个相邻状态的 min 加一，再用滚动一维数组把空间压到 O(m)。

完全背包方案计数：外层按面值分层保证不重不漏，内层金额正序枚举允许面值无限复用，f[m] 即组合方案数。

一维滚动 0/1 背包 DP：逐件物品倒序扫描容量，dp[v]=max(dp[v],dp[v-W]+C)，答案为 dp[M]。

完全背包模板题：容量正序枚举，同一种物品可重复选取。

一维 dp[j] 表示容量 j 的最大价值；完全背包正序更新，01 与多重背包倒序更新，多重背包用二进制拆分。

多重背包：把每种奖品的限购 s 二进制拆分成若干份捆绑，转成 0/1 背包求解最大总价值。

以每个位置为峰值，正向 LIS 得左段、反向 LIS 得右段，rise[i]+fall[i]-1 的最大值即最多保留人数，N 减之即为答案。

二维 DP 求两串最长公共子序列，滚动数组压到 O(m)。

边都从小编号指向大编号的 DAG 上求点权和最大的路径：倒序 DP，dp[u] = a[u] + max(dp[v])，用 nxt 数组还原路径。

用 f[i] 表示以第 i 个数结尾的最长不下降子序列长度，枚举前面更小的 j 转移，O(n²) 求出最大长度。

DAG 最短路：边只从小城市指向大城市，编号即拓扑序，逆序 DP f(i)=min(w(i,j)+f(j)) 并用 go 数组回溯，O(N²) 求 1→N 最小费用与路径。

把可通行格建成无权无向图，四方向 BFS 逐层扩展，层号就是最少步数；入队即标记保证每格只展开一次，不连通时无输出。

把迷宫看作无权图，从 S 出发做一次 BFS，首次到达 E 的步数即为最短时间；若 E 不可达则输出 oop!。

网格四连通 BFS，起点距离为 0，首次到达终点时的层号即最少步数。

值域是整个 int 范围不能开桶，用 set 去重并自动保持升序，时间 O(n log n)。

八连通洪泛填充：扫描棋盘遇到未访问的 W 就计数，并用迭代栈把它所在整片连通水洼就地从 W 改写成 .。

排序后首尾双指针夹逼两数之和：和偏小放弃整行、和偏大放弃整列，首次命中天然就是题面要求的较小数最小的数对。

五次多项式无求根公式，用题面给出的异号端点与区间内唯一根作前提，实数二分 40 轮后输出中点。

长度乘 100 化成厘米整数后，切出段数随切割长度单调不增，在 [0, max+1] 上开区间二分最大可行长度，O(n log V) 求解，无解由 lo=0 哨兵统一输出 0.00。

二分最大段和，用贪心验证能否在不超过 M 段内完成划分。

在非降序列上二分定位插入位置，比较夹住询问值的左右相邻元素，距离相等时取较小值，单次询问 O(log n)。

利用根是两位小数且两根之差至少为 1 的约定，在 [-100,100] 上以 0.01 步长从左到右扫描，命中 |f(x)|≤1e-5 的网格点即根，三次命中天然有序。

逆序对只依赖相对大小，先把值离散化为排名 1..n，再用权值树状数组从左到右「先查前缀和、后单点插入」，每次增量 = 已插入个数 − 前缀和，O(n log n)。

用 map 统计每个数字出现次数，按键升序输出。

把数组降序排序后取前 k 项逐行输出；用 sort + greater<ll>() 翻成降序后取前 k 个。

每个龙头完工时刻等于分给它的人的水量之和，故用最小堆维护各龙头累计接水量，新人接到最早空出的龙头，O(n log m)。

按左端点排序后维护已并入区间的最大右端点 reach，一旦某个左端点越过 reach 就出现断口、输出 no，否则答案为最小左端点与最终 reach。

两节电池同时放电：总电量给出上界 Σ/2，单节速率上限再给出上界 Σ−max，答案取小者，按比例换电即可取到。

排序后按最慢者递推：最快者往返快递一人，或两名最快者摆渡两名最慢者，逐个取较小值。

删 k 位等价于留 m-k 位的子序列：用单调栈一次扫描，每步把大于当前数位的栈顶弹出（等于花一次额度把更小的数位提到前面），扫完后若还有额度则砍掉末尾若干位。

按 x 降序、y 降序排序后一次扫描：已扫过点都满足 x' ≥ x，故当前点被支配当且仅当 y 不大于已扫过的最大 y，判定降为 O(1)，总复杂度 O(n log n)。

贪心：把奶牛按高度从大到小排序，优先选最高的奶牛叠放，累计高度首次达到书架高度 B 时用掉的奶牛数即为答案。

Charley 0 时刻从起点出发，途中遇到更快的人就跟上去；答案就是 t>=0 的同行人中 t + ceil(16200/v) 的最小值。

求最小的比 n 大、且二进制中 1 的个数与 n 相同的数：对最低位 1 做一次 Gosper 进位，再把被清空的 1 补回最低位，单次 O(1)。

部分背包模板：按单位重量价值降序贪心，能装全装、装不下就切一部分。

≤5×5 棋盘上从给定起点出发、马走日不重复的全遍历路径条数，回溯按邻接表枚举合法马步，位图维护已访问集合。

Euclid 博弈：商 ⌊a/b⌋ ≥ 2 或整除时执子者必胜，商为 1 时取法唯一、胜负随轮次翻转，辗转相除 O(log V) 模拟到首个可胜局面即可。