动态规划优化：前缀和、单调队列与斜率优化

看到两层循环，能不能把里面那层换成单调队列？不一定。看到一个平方，能不能直接套斜率优化？也不一定。

优化不是给代码换一个更高级的容器，而是剥开公式的洋葱皮，找到我们在反复计算的内容，并证明哪些工作可以合并、哪些候选人可以永远淘汰。本篇我们不再重讲单调队列的基础模板，而是解决如何从转移式子中认出窗口，实施真正的降维打击。

先修建议：《单调队列思想》第四节的滑动窗口模板、第九节的 DP 式子识别，以及《动态规划基础》第五节的多重背包。主课读一至五节，再读第八节收尾；第六、七节按需选学。

一、优化的心法：先写出“前驱什么时候可用”

很多同学学 DP 优化，喜欢直接背数据结构模板，这是本末倒置。

假设原式是 $f[i] = \min_{j < i} \{f[j] + w(j,i)\}$ 。开始优化前，你必须先回答灵魂拷问： f[i] 的物理意义是什么？哪些 j 是合法的候选人？这些 f[j] 算好了吗？每次到底在重复计算什么？

如果连合法范围都没写清，数据结构维护得再漂亮，也可能把未算完的自己当成自己的前驱。优化应该保留原转移，只是更快地算它，而不是悄悄放宽条件。

二、第一层剥洋葱：重复的区间求和，用前缀和收起来

一个课堂小模型：从第 0 级台阶出发，每次能走 1 到 $k$ 级，问走到第 $n$ 级有多少种走法，对 $10^9+7$ 取模。定义 f[i] 为恰好走到第 i 级的方案数，f[0]=1，这 1 种是还没迈步的空走法。

最后一步可以从哪里来？只能是跨了不超过 $k$ 步的地方，即 $\max(0, i-k) \le j < i$ ：

f[i] = \sum_{j=\max(0,i-k)}^{i-1} f[j]

痛点在哪里？如果 $k=2$ ，计算 f[4] 是求 f[2]+f[3]，计算 f[5] 是求 f[3]+f[4]。相邻两轮的求和区间几乎相同，没必要每次扫一遍！

这层的降维打击，靠的是把区间和拆成两个前缀。定义灵魂数组 $s[i] = f[0] + \dots + f[i]$ ，并约定边界 s[-1]=0。设左边界 $l = \max(0, i-k)$ ，就有：

f[i] = s[i-1] - s[l-1]

原本需要

O(nk)

的时间，现在先算 f[i]，再把它加入 s[i]，总时间瞬间降为

O(n)

。

(注：代码中 $l=0$ 时直接减零即可；取模减法必须加模数后再取模。s[0] 初始化为 1，否则出发点的走法就全消失了。)

三、第二层降维：多重背包的枚举次数，怎样拍扁成滑动窗口？

已有二进制拆分能解决多重背包。现在试着不拆物品，直接处理一整种物品。设当前物品价值 $v$ 、重量 $w$ ，最多取 $c$ 件。g[j] 是处理当前种类之前，总重量不超过 $j$ 的最大价值；f[j] 是加入这一类后的结果。最朴素的转移是：

f[j] = \max_{0 \le k \le c,\ kw \le j} \{g[j-kw] + kv\}

痛点：这看着一点都不像连续窗口，因为前驱每次隔了 $w$ 。

1. 物理视角的转换：按余数分组

既然隔着 $w$ 跳，那我们就把容量按除以 $w$ 的余数分组！固定余数 $r$ ，只看 $r, r+w, r+2w, \dots$ ，只有这些位置之间才会互相转移。

把当前容量写成 $r + tw$ ，前驱写成 $r + uw$ ，选取的件数就是 $t - u$ 。重新整理式子：

f[r+tw] = tv + \max_{\max(0,t-c) \le u \le t} \{g[r+uw] - uv\}

这下窗口出来了！外面的 $tv$ 是本轮固定量；候选分值 $g[r+uw] - uv$ 在这一种物品的处理过程中不会变；而合法的下标窗口 $[\max(0,t-c), t]$ 就是一个从左到右滑动的标准窗口。

2. 手推一次过期，体会数量限制的物理意义

假设有个物品 w=3, v=5, c=2。我们在算容量 9 的时候（此时组内余数 r=0，容量 $9 = 0 + 3 \times 3$ ，即 $t=3$ ）。合法的前驱 $u$ 从哪里到哪里？最多拿 2 件（ $c=2$ ），所以 $u$ 最小只能是 $3-2=1$ 。合法前驱就是 $u=1, 2, 3$ 。如果队列里最好的候选人是 $u=1$ ，说明我们选择在前驱状态 g[3]=4 的基础上，加上 2 件新物品（ $2 \times 5 = 10$ ），最终得到 f[9]=14。

多重背包余数组示例：w=3、v=5、c=2，容量9对应t=3，合法前驱u=1至3，选择g（3）=4加两件得到f（9）=14。

如果队首的 $u=0$ 没过期，会得到 15，看起来更赚，但这实际上取了 3 件新物品。窗口的左边界不是实现细节，它就是题目的数量限制。

3. 为什么必须先入队，再取答案？

因为 $u=t$ 表示当前物品选 0 件，完全合法！而入队的值必须来自干净的旧层 g，不依赖正在计算的 f。如果直接读取已经更新过的 f[r+uw]，候选可能已经拿过当前物品了，这就相当于绕开了件数限制又拿一次。别把“每个容量只赋值一次”误当成不会重复取物品的保证。

物理意义与手算验证：假设只有一种物品，重量 $w=2$ 、价值 $v=3$ ，最多拿 1 件（ $c=1$ ）。最初容量为 0、2、4 的最大价值都是 0。

算容量 2 时，拿一件得到 f[2]=3。
算容量 4 时，若误把已更新的 f[2] 当作旧层前驱，再加 3 就得到 6；正确的旧层 g[2]=0，所以最多仍只能得到 3。

这样错在绕过了件数上限。本篇用 g = f 保存历史快照，队列只从 g 提取候选，结果写进 f，把读层与写层隔开。若要省掉拷贝，也必须在覆盖某个位置前保存它的旧层候选值，不能把新值回灌进队列。

4. 完整程序一：单调队列优化多重背包

💡 【实战接口】 输入 $n, W$ ，随后每行 $v, w, c$ ；输出不超载时的最大价值。课堂范围 $0 \le n \le 100$ ， $0 \le W \le 40000$ ， $0 \le v,c \le 10^9$ ， $1 \le w \le 10^9$ 。允许什么都不选，不要求装满。（此代码接口可直通洛谷 P1776 宝物筛选）。

运行样例： 输入：

2 10
6 3 2
4 2 2

输出：

每种物品的各个余数组合起来，恰好遍历每个容量一次，时间 $O(nW)$ ，空间 $O(W)$ 。重量超过容量直接跳过；数量截断到 $W/w$ ，再多也装不进去。

#include<bits/stdc++.h>
#define int long long
using namespace std;

void solve(){
	int n, W;
	if(!(cin >> n >> W)) return;
	vector<int> f(W + 1, 0); // f[0..W]全为0，对应“不超过容量”的初值
	
	for(int i = 1; i <= n; i++){
		int v, w, c;
		cin >> v >> w >> c;
		if(w > W || c == 0) continue;
		c = min(c, W / w); // 再多也装不下
		
		vector<int> g = f; // 必须复制一份旧层，保证拿取件数的物理意义
		for(int r = 0; r < w; r++){
			deque<pair<int, int>> q; // 存 {下标 t, 候选分值}
			for(int t = 0, j = r; j <= W; t++, j += w){
				// 1. 队首淘汰过期候选 (u < t-c)
				while(!q.empty() && q.front().first < t - c) {
					q.pop_front();
				}
				
				// 2. 当前前驱入场，队尾淘汰弱鸡
				int z = g[j] - t * v; 
				while(!q.empty() && q.back().second <= z) {
					q.pop_back();
				}
				q.push_back({t, z});
				
				// 3. 队首就是窗口最大值，结算 f[j]
				f[j] = q.front().second + t * v;
			}
		}
	}
	cout << f[W] << '\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

四、第三层降维：候选的好坏会随查询位置变化

普通单调队列比较的是固定分值。但如果候选 A 的得分是 $2x+1$ ，候选 B 是 $x+5$ ，谁小？ $x=1$ 时 A 小， $x=10$ 时 B 小。如果只看加入时谁更好就把另一个删掉，就会出错。

这类候选是一条条直线，查询时问某个横坐标处谁最低。我们用有明确单调条件的玩具装箱来推一遍凸包优化（斜率优化）。

1. 状态和平方从哪里来？

💡 【实战例题：玩具装箱】 摆放 $n$ 件玩具，长度为 $C[i]$ 。同箱相邻玩具间加 1 单位填充。实际箱长为 $x$ ，理想箱长为 $L$ 时，费用是 $(x-L)^2$ 。求最小总费用。

定义 f[i] 为装好前 i 件的最小总费用，f[0]=0。设 $s[i] = \sum_{k=1}^{i}(C[k]+1)$ 。最后一箱如果装第 $j+1$ 到 $i$ 件（ $0 \le j < i$ ），它的实际长度正好是 $s[i] - s[j] - 1$ 。再令查询位置 $x = s[i] - L - 1$ ，转移方程为：

f[i] = \min_{0 \le j < i} \{f[j] + (x - s[j])^2\}

将其完全展开并整理：

f[i] = x^2 + \min_{0 \le j < i} \{-2s[j]x + f[j] + s[j]^2\}

对于每个已完成的前驱 $j$ ，这就建起了一条直线：

斜率 $k = -2s[j]$
截距 $b = f[j] + s[j]^2$

当前的任务，就是在求 f[i] 时，查询这些直线在横坐标 $x$ 处的最小值！

2. 什么时候能用队列维护这些直线？

本题玩具长度 $C[i] \ge 1$ ，这赋予了式子极强的物理单调性：前缀和 $s[i]$ 严格递增。所以：加入的斜率严格递减，查询位置也严格递增。这两条单调性让我们能安全地从队列两端淘汰候选：

队首淘汰：前两条线在当前 $x$ 处的值比对。如果第二条线已经不大于第一条线，由于第二条线斜率更小（下降更快），未来 $x$ 继续增大时只会更占优势，第一条线就可以永久退出。
队尾淘汰：检查斜率递减的三条线 $a, b, c$ 。若 $a, b$ 的交点不早于 $b, c$ 的交点，意味着 $b$ 还没来得及胜过 $a$ ，就已经被 $c$ 彻底接管，成了没用的备胎。

交点横坐标为 $\frac{b_b - b_a}{k_a - k_b}$ 。分母为正，直接交叉相乘避免浮点除法：

(b_b - b_a)(k_b - k_c) \ge (b_c - b_b)(k_a - k_b)

满足就删掉中间的

b

。

3. 时序逻辑的闭环：先查询，后加入

绝不能让尚未算好的自己来给自己报价！合法前驱要求 $j<i$ ，因此必须先通过队首查询得到 f[i]，再把它转化为第 $i$ 条直线加入队尾。

4. 完整程序二：单调凸包优化玩具装箱

输入 $n, L$ ，再输入 $n$ 个长度 $C[i]$ ；输出最小费用。支持 $0 \le n \le 50000$ ， $1 \le L, C_i \le 10^7$ 。（对接洛谷 P3195 [HNOI2008] 玩具装箱）。

运行样例： 输入：

2 3
1
1

输出：

溢出警告：虽然最终答案最优值不超过 $50000 \times (10^7-1)^2 < 5 \times 10^{18}$ （long long 能存下），但中间过程的截距 $s^2$ 和交叉乘积可达 $10^{36}$ 量级。本程序使用 GCC 编译器支持的 __int128 承接中间运算，强转放在乘法之前，彻底消灭溢出隐患。这不是任意大整数模板，请放心使用。

#include<bits/stdc++.h>
#define int long long
using namespace std;

// 128位宽整数，降维打击防溢出
typedef __int128_t i128;

struct Line {
	int k;
	i128 b;
};

// 计算直线在 x 处的值
i128 get_val(const Line& a, int x){
	return (i128)a.k * x + a.b;
}

// 判断中间的线 b 是否成了无用的备胎
bool bad(const Line& a, const Line& b, const Line& c){
	return (b.b - a.b) * (b.k - c.k) >= (c.b - b.b) * (a.k - b.k);
}

const int N = 50005;
Line q[N];
int head = 1, tail = 0;

void solve(){
	int n, L;
	if(!(cin >> n >> L)) return;
	
	int s = 0, f = 0;
	
	// 初始化前驱 0：j=0 时，f[0]=s[0]=0，对应直线 k=0, b=0
	q[++tail] = {0, 0};
	
	for(int i = 1; i <= n; i++){
		int c;
		cin >> c;
		s += c + 1;
		int x = s - L - 1;
		
		// 1. 队首淘汰：若第二条线在 x 处已不差于第一条，第一条永久退出
		while(head < tail && get_val(q[head], x) >= get_val(q[head+1], x)){
			head++;
		}
		
		// 2. 取最优直线结算 f[i]
		f = (int)((i128)x * x + get_val(q[head], x));
		
		// 3. 把算好的状态封装成直线准备入队
		Line cur = {-2 * s, (i128)f + (i128)s * s};
		
		// 若斜率相同，保留截距更小的，防止除数为0
		if(head <= tail && q[tail].k == cur.k){
			if(q[tail].b <= cur.b) continue;
			tail--;
		}
		
		// 4. 队尾淘汰：如果新线让队尾变成备胎，弹掉队尾
		while(head < tail && bad(q[tail-1], q[tail], cur)){
			tail--;
		}
		
		// 5. 正式入队
		q[++tail] = cur;
	}
	cout << f << '\n';
}

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

五、滚动数组与转移层隔离

读哪个层、写哪个层，要先按原转移式分清。 01 背包靠容量倒序保护旧值；本篇多重背包用 g = f 隔离读写。具体的件数反例已放在第三节第 3 小节，忘了就回头手推容量 2 和 4。

六、当斜率或查询不再单调：换工具的衔接（选学）

先修提示：需掌握二分查找，或了解基础的平衡树/分治思想。

在玩具装箱问题中，玩具长度都是正数，这给了我们极其完美的单调性：加入的直线斜率单调递减，查询的横坐标 $x$ 单调递增。如果这两条性质被打破，还能用斜率优化吗？能，但不能用简单的双端队列了。

1. 查询位置 $x$ 不单调：换用二分查找

场景：如果查询位置 $x$ 忽大忽小，我们就不能执行“队首淘汰”。因为一个在小 $x$ 处不够优秀的直线，等到 $x$ 变大后，完全可能因为斜率优势再次成为最优解。

解决策略：保留完整的凸包。因为凸包上的直线斜率依然是有序的，它们各自成为最优解的 $x$ 区间也是单调的。我们在凸包上直接进行二分查找。

代码片段（替换玩具装箱中的队首淘汰和取值部分，依赖原有的队列 q 和有效区间 [head, tail]）：

int l = head, r = tail, best_idx = tail;
while (l <= r) {
	int mid = l + (r - l) / 2;
	// 如果 mid 处的线在 x 处不如 mid+1 的线优秀，说明最优切点还在右侧
	if (mid < tail && get_val(q[mid], x) >= get_val(q[mid+1], x)) {
		l = mid + 1;
	} else {
		best_idx = mid;
		r = mid - 1;
	}
}
f = (int)((i128)x * x + get_val(q[best_idx], x));

2. 新加入的斜率 $k$ 不单调：换用高级数据结构

场景：如果物品存在负数，导致计算出的斜率忽大忽小，我们就不能简单地在队尾淘汰备胎了。新来的直线可能直接插进凸包的中间，摧毁了队列的单调性。

解决策略：这就需要动态维护凸包。我们必须果断丢弃单调队列，切换到以下工具：

李超线段树 (Li Chao Tree)：专门用于维护多条直线，支持任意位置插入和查询最值，代码比手写平衡树短得多。
CDQ 分治：把动态加线的问题，离线转化为先按斜率排序好的静态加线问题。

小结：看到带有乘积项的转移方程，推导出直线方程后，不要立刻默写双端队列。先确认斜率 $k$ 和查询点 $x$ 是否单调！ 缺了哪一个，就换对应的工具补上。

七、决策单调性的适用条件与反例意识（选学）

先修提示：需熟练掌握经典的 $O(n^3)$ 区间 DP。

很多同学在做区间 DP 时，听说过一个神仙优化：原本 $O(n^3)$ 的三重循环，只要加上决策单调性，就能降到 $O(n^2)$ 。于是见题就套，这是考场大忌。

什么是决策单调性？ 假设状态 $f[i][j] = \min_{k} \{ f[i][k] + f[k+1][j] \} + w(i, j)$ ，它的最优分割点是 $opt(i, j)$ 。如果这个分割点满足： $opt(i, j-1) \le opt(i, j) \le opt(i+1, j)$ ，也就是当你把区间的右端点向右拉长时，最优分割点绝不会向左倒退。我们就可以把 $k$ 的枚举范围限制在 $[opt(i, j-1), opt(i+1, j)]$ 之间，直接完成降维。

1. 手算真假判定：石子合并 VS 矩阵连乘

正例：非负重量石子合并的最小代价版本 代价函数 $w(i, j)$ 是区间石子的总重量，它满足区间包含的单调关系与四边形不等式（交叉相加 $\le$ 包含相加）。这里讨论的是取最小值，不能直接把结论套到最大代价版本。直观上，右边新增了一堆大石子，为了整体代价最小，最优合并缝隙 $k$ 理应往右靠，去平衡两边的重量。它的 $opt$ 表格是稳步向右下角推进的，可以用决策单调性。

致命反例：矩阵连乘 在求矩阵连乘的最小运算次数时，假如矩阵维度是 A: 10x100, B: 100x5, C: 5x50, D: 50x1。

只看 $ABC$ ： $(AB)C$ 的代价是 $10\times100\times5+10\times5\times50=7500$ ； $A(BC)$ 的代价是 $100\times5\times50+10\times100\times50=75000$ 。所以最佳分割点是 $opt(1,3)=2$ 。
加入右边的 $D$ 后： $B(CD)$ 的代价是 $5\times50\times1+100\times5\times1=750$ 。最外层按 $A\mid BCD$ 分割，总代价为 $750+10\times100\times1=1750$ ；按 $AB\mid CD$ 分割为 $5300$ ，按 $ABC\mid D$ 分割为 $8000$ 。所以 $opt(1,4)=1$ 。

区间变长了，最佳分割点却从 2 退回 1！矩阵连乘的合并代价是 $p_{i-1}p_kp_j$ ，依赖分割点 $k$ ，不是前面只与区间端点有关的 $w(i,j)$ ；不能照搬石子合并的决策范围。

考场避坑法则：决策单调性不是免费的常数优化！如果你不确定题目满不满足四边形不等式，先写个朴素的 $O(n^3)$ 暴力，把小样例的 $opt[i][j]$ 表格打印出来。如果表格的数字出现明显的“倒车”（比如 $j$ 变大了，最优决策点反而向左跑了），立刻住手，绝不能强行套用决策单调性的范围限制！

八、灵魂拷问：优化到底省掉了什么？

最后，我们回头看看：优化前后，哪些东西不能偷偷换掉？不要看代码都用了一个 while 和队列，就以为它们是同一种套路。

前缀和：维护的是已算好的方案数之和。它省掉了每次求和的扫描。
单调队列（多重背包）：维护的是旧层扣掉线性项后的窗口最大值。它省掉了枚举“当前物品选几件”。
斜率优化（凸包）：维护的是不同斜率候选直线在查询位置的最小值。它省掉了枚举“最后一箱的起点在哪”。

外层的状态，依然乖乖按照它原本的物理依赖顺序在计算。如果你优化完，连状态含义、可选范围都解释不清了，请立刻退回到朴素转移，而不是继续给数据结构打补丁。解释不了的时候，先别把正确的慢程序换成一个跑得飞快的错误答案。

练习顺序：先做 P1776《宝物筛选》，练习从件数限制推出余数组窗口；再做 P3195《玩具装箱》，练习展开平方、认出直线并检查两种单调性。两题的输入接口分别见第三、四节。

动态规划优化