从 TLE 到稳 AC:我刷题攒下的 C++ 实战经验
刷题时明明思路对了却总吃 TLE,后来才发现坑都藏在细节里。这篇记录我在容器选择、输入输出、递归递推和 C++17 新特性上踩过的坑,也聊聊模板化的代价。
支持通配符SSL证书、多域名证书、IP证书。适配ACME接口, 支持Zerossl、Let's Encrypt和Google等渠道。登录已有账号
2026-10-23 17:16:01 动态规划 状压DP 算法竞赛 洛谷题解
上个月啃洛谷 P8162《让我们赢得选举》,我交了一版 3^N 的状压,然后对着屏幕发了半分钟呆。题面挺亲切:N 个州,N 到 500,候选人 Rie 要拿下至少 K 张票。在一个州累计演讲满 A_i 小时,这州的一票到手;继续撑到 B_i 小时(有的州 B_i 是 -1,没这选项),还能招募一名本地协作者。人多力量大是字面意义的,p 个人同时在一个州演讲,进度每小时就推 p。从孤身一人出发,问最少几小时凑齐 K 票。
翻车很典型,手比脑子快。每州不去、拿票、拿人三态,f[mask] 状压是肌肉记忆。写完才反应过来这是 3^N,不是常数问题,是指数问题。哪怕退一步,只枚举哪些州用来招人,也还是 2^N。状压在这里注定死,因为想做到不重不漏,就得把选过哪些州整个记下来,除非最优解本身自带结构。

冷静下来先盘问题。一个州只有三档值得停:0、A_i、B_i。停在中间不产生收益,半途而废的进度也不保留,决策天然离散。麻烦在于人数随招聘实时变化,每州耗时等于档位除以当时人数。好在人数这个维度有限,招满 k 人封顶,k 不会超过 K,至多 500。把 k 拿到外层枚举掉,分母立刻全变常数,这就是多项式解能立起来的底气。
接下来是四条靠交换论证挖出来的结构性质。一,全员集中攻同一个州。人力劈成两摊永远不如先合力做完一州,早一刻完成就早一刻多一个人帮忙,方案就此退化成一条串行流水线。二,招人州按 B 升序排队。第 j 个被攻克的招人州由 j 个人一起做,贡献 B/j,权重 1/j 递减,小的 B 配大权重和最小,排序不等式一锤定音。三,纯拉票州不插在招人州前面。拉票不换人,排到手最齐的压轴段才划算,于是决策顺序大半被排死。四,压死指数的那一条:若 B 大的州成了招人州,B 比它小的州绝不会被放弃,两者对调,招人成本只降不升。设 B 值最大的那个招人州排在位置 i,则前 i 个州必然全部入选,i 之后只允许纯拉票的州。
形状定了,DP 顺水推舟。州按 B 排序后,f[i][b] 表示前 i 个州全部选入、其中 b 个是招人州的最小耗时。前缀只需两维,靠「全选」约束把拉票州个数钉死成 i-b,没有第三维可写。转移就两行:下一州当招人州,由 b+1 人合力,加 B/(b+1);当拉票州,它真实的工作时段在人最齐的收尾,加 A/(k+1)。后缀预处理 g[i][j],从第 i 个州起挑 j 个拉票州的最小 ΣA,只存原始进度和,除法整体后提。分母对固定 k 是公共因子,缩放不改变谁最小,这正是前缀优化敢省掉一维的单调性前提。收尾时枚举招人段停在的前缀长度 i,候选答案 f[i][k]+g[i+1][K-i]/(k+1),k 与 i 各扫一遍 1 到 K,配上 O(N^2) 的 g,总账 O(N^3),N=500 跑满无压力。k=0 即一个人拉票的兜底情形由 g[1][K] 直接给出。
核心代码不长,两个角色各自交代清楚:
// x 已按 B 升序排序(B=-1 视作 INF), K 为目标票数
// g[i][j]: 第 i..n 个州里挑 j 个纯拉票州的最小 ΣA
for (int i = n; i >= 1; --i)
for (int j = 0; j <= K; ++j) {
g[i][j] = g[i+1][j];
if (j) g[i][j] = min(g[i][j], g[i+1][j-1] + x[i].a);
}
double ans = g[1][K]; // k=0: 孤身一人把所有票拉完
for (int k = 1; k <= K; ++k) { // 枚举招人州总数
f = INF; f[0][0] = 0; // f[i][b]: 前 i 州全选入、b 个招人州
for (int i = 0; i < n; ++i)
for (int b = 0; b <= min(i, k); ++b) {
upd(f[i+1][b+1], f[i][b] + x[i+1].b/(b+1)); // 第 b+1 个招人州
upd(f[i+1][b], f[i][b] + x[i+1].a/(k+1)); // 拉票州压轴做
}
for (int i = k; i <= K; ++i) // 招人段收尾于前缀 i
ans = min(ans, f[i][k] + g[i+1][K-i]/(k+1));
}
题解最怕「我觉得对」。我在自己小站上搭了个对拍器,暴力陪跑那半边贴在这里,它对排序、前后缀那些性质一无所知,只默认了流水线这一件事:
// 暴力: 枚举每州三态(0 不去/1 拉票/2 招人), 内层子集 DP 试尽一切完成顺序
for (let code = 0; code < 3**n; code++) {
const as = []; let c = code;
for (let i = 0; i < n; i++) { as.push(c % 3); c = (c / 3) | 0; }
const sel = [...as.keys()].filter(i => as[i]);
if (sel.length < K) continue;
if (sel.some(i => as[i] === 2 && B[i] < 0)) continue; // 无 B 不可招人
const dp = Array(1 << sel.length).fill(Infinity);
dp[0] = 0;
for (let mask = 0; mask < dp.length; mask++) {
if (!(dp[mask] < Infinity)) continue;
let w = 1; // 人数 = 1 + 已招到的
for (let j = 0; j < sel.length; j++)
if ((mask >> j & 1) && as[sel[j]] === 2) w++;
for (let j = 0; j < sel.length; j++) if (!(mask >> j & 1)) {
const i = sel[j], t = as[i] === 2 ? B[i] : A[i];
dp[mask | 1 << j] = Math.min(dp[mask | 1 << j], dp[mask] + t / w);
}
}
best = Math.min(best, dp[dp.length - 1]);
}
N 压到 8,随机跑了 1000 组数据,四种形态各占四分之一:大量 -1、全无 -1、清一色 -1、B 值互相撞车专门卡排序稳定性。暴力与 DP 零不一致,五个官方样例也全对。对拍全绿,我才敢把上面这段转移贴进正文。
对拍脚本和题解页面都挂在我的校园服务器上。有回深夜提交整页报错,我逐行排查代码找 WA 来源,查了一个小时才意识到根本不是算法的事:站点 HTTPS 证书到期,提交页和评测脚本一起哑火。后来接了 lcjmSSL 的轻量 API,证书申请、验证、部署全自动,到期前自己续签,这种「WA 其实是证书」的乌龙从此绝迹。
同类题型可以打包记一下。凡是前期投入改变后期单价的资源分配、多阶段选择、带额外收益项的预算型 DP,套路都是先把红利总量拿到外层枚举,让分母变常数,再看决策能不能排序、前后缀能不能拼接。顺序可交换加上档位离散,往往就是多项式解存在的全部信号。反过来,要是协作者各有效率、州的加成是非线性的,交换论证当场断链,多项式解很可能压根不存在,这时候别硬凑状态,该往近似、剪枝想,或者退回 2^N 折半碰运气。结构性质挖不出来,这件事本身就是结论。
刷题时明明思路对了却总吃 TLE,后来才发现坑都藏在细节里。这篇记录我在容器选择、输入输出、递归递推和 C++17 新特性上踩过的坑,也聊聊模板化的代价。