2026/6/29/XL课堂笔记(最大字段和)
课堂笔记 · 2026-06-29 ·
🧠 核心套路总结
专题A：二进制枚举（位运算子集枚举）
模板
for (int i = 0; i < (1 << n); i++) { // 枚举 0..2^n-1 所有选法
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) { // 第 j 位是 1 = 选中
// 处理
}
}
// 累加答案
}
适用场景
- n ≤ 20：可枚举 2^n 个子集
- 每个物品 选/不选
- 对子集做约束判断
你的代码风格
- 用
tj[30]数组标记当前选中的元素 - 每次循环结束清零（注意：必须在判断后再清空！）
- T = 配料数（n），N = 限制数（t），数据范围都对得上
专题B：线性DP - 最大子段和族
核心方程：前缀和 + 区间最小前缀
s[i] = s[i-1] + a[i]; // 前缀和
mi[i] = min(mi[i-1], s[i]); // 最小前缀
ans = max(ans, s[i] - mi[i-k]); // 长度=k 的最大子段
进阶1：长度至少为 k 的最大子段和（5664）
// 关键：枚举右端点 i，长度∈[k, i] 的最大和 = s[i] - min(s[0..i-k])
for (int i = k; i <= n; i++) {
int l = i - k + 1;
ma = max(ma, s[i] - mi[l-1]); // mi[l-1] = min(s[0..l-1])
}
思路：固定右端点 i，子段最短 k 个 = 从左端点 ≤ i-k+1 起步。要 s[i] 最大且 min prefix 最小。
进阶2：双段最大子段和（5353）
思路：枚举分割点 k，把序列切成 [1..k] 和 [k+1..n]，两边各取最大子段和。
dp[i] = max(a[i], dp[i-1] + a[i]); // 前缀最大子段和
dp2[i] = max(a[i], dp2[i+1] + a[i]); // 后缀最大子段和（从右往左）
ma[i] = max(ma[i-1], dp[i]); // 前缀最大
ma2[i] = max(ma2[i+1], dp2[i]); // 后缀最大
for (int k = 1; k < n; k++)
ans = max(ans, ma[k] + ma2[k+1]); // 枚举分割点
进阶3：相邻不能同时选（5352 大盗阿福）
经典DP：dp[i] = max(dp[i-1], a[i] + dp[i-2])
- 不抢第 i 家 →
dp[i-1] - 抢第 i 家 →
a[i] + dp[i-2]（跳过相邻的 i-1） - 初值：
dp[1] = a[1]
进阶4：乘积为正/负的子区间（5356 判正负）
关键观察：乘积的正负性 = 负数个数的奇偶性。
dp[i]= 以 i 结尾、乘积为负的子区间数dp2[i]= 以 i 结尾、乘积为正的子区间数- 转移：
if (a[i] > 0) { dp[i] = dp[i-1]; // 负区间延续，符号不变 dp2[i] = dp2[i-1] + 1; // 新增正区间（只有a[i]自己） } else { dp[i] = dp2[i-1] + 1; // 翻转 dp2[i] = dp[i-1]; } - 最后
ans_负 = Σdp[i],ans_正 = Σdp2[i]
⚠️ 易错点清单（今日 2 次 WA 的根因）
❌ 错点1（5266 比萨）：tj 数组清零时机
- 症状：WA on 样例
- 根因：在
flag==1判断之前未清零 tj，或在判断后忘记清零导致下个子集污染 - 修正：循环末尾统一
memset或 for 清零
❌ 错点2（5664 长度≥k最大子段和）：初值边界
- 症状：WA on 边界
- 根因：
mi[0]必须初始化为 0（前缀和为 0 时长度为 k 的子段可以从前缀起点开始）。如果mi[0] = 1e18就会让"以第一个元素为右端点、长度=k"的子段错过最优解 - 修正：
mi[0] = 0;或mi[0] = s[0]
❌ 错点3（5353 双段最大子段和）：初始化负无穷
maa = -1e9必须在每个 t 循环内重置，否则累加造成答案偏大
❌ 错点4（5356 判正负）：翻转顺序
dp[i] = dp2[i-1] + 1必须在dp2[i] = dp[i-1]之前——因为新值依赖旧值
🧩 题型演化路线（线性DP最大子段和族）
最大子段和（基础，单段）
│
├── 加约束：长度≥k → 5664（用前缀和+min前缀）
├── 加维度：选两段 → 5353（前后缀DP+枚举分割点）
├── 加约束：相邻不选 → 5352（dp[i] = max(dp[i-1], a[i]+dp[i-2])）
└── 改判定：乘积符号 → 5356（正负计数DP，翻转转移）
最大子段和是核心——五种题都在这基础上加约束/加维度/改目标函数。背熟：
dp[i] = max(a[i], dp[i-1] + a[i]) // 选 a[i] 或接在前一个后面
📅 学习曲线（时间线）
17:40 ━━ 陈老师加油 1次AC（warm-up，二进制枚举）
17:43 ━━ 比萨 1WA→AC（tj数组清零失误）
18:01 ━━━ 长度≥k最大子段和 1WA→AC（mi[0]初值边界）
18:29 ━━━ 双段最大子段和 1WA→AC（maa重置）
19:04 ━━━━ 大盗阿福 1WA→AC（dp[1]初值）
19:22 ━━━━━ 判正负 1WA→AC（翻转顺序）
观察：每次 WA 都在 5分钟内 修正，调试速度非常快。说明思路正确，差的只是细节（边界/初值/清零），这是成长最快的阶段。
🎯 复习重点（建议反复练）
- 前缀和 + 最小前缀 模式 → 5664、5353 的核心
- dp[i] = max(dp[i-1], a[i]+dp[i-2]) → 相邻约束类题（如打家劫舍、采药）
- 二进制枚举 tj[]清零 → 任何子集题的关键
- 状态翻转转移（dp和dp2互换 +1）→ 乘积正负类
- 初值！初值！初值！：mi[0]=0, dp[1]=a[1], maa=-INF
📌 今日金句
"思路对但细节错" = 离 AC 只差 1 个
mi[0]=0的距离 🚀