椰程信奥 · 限时训练单
动态规划1 · 限时训练单（50 分钟 · A/B 双卷 · 三题）
训练说明
| 项目 | 内容 |
|---|
| 题量 | 3 题：HERB 采药（01 背包）／HERB2 疯狂的采药（完全背包）／MISSILE 导弹拦截（LIS） |
| 时长 | 50 分钟。闹钟一次设定，不暂停、不查资料、不回看课件。 |
| 分层 | A 卷＝冲满分路线；B 卷＝保部分分路线。由教练按上次成绩分派，学生不自选。 |
| 纪律 | 时间到立即停手并提交。没写完的正解也要先把当前能过的版本交上去。 |
一、时间盒（50 分钟）
| 时段 | 时间 | 做什么 | 做完的标志 |
|---|
| 第 1 段 | 0–5′ | 三题全部读一遍，在题号旁写下"这题像哪种模型"和"我先拿哪一档" | 三行字写完 |
| 第 2 段 | 5–20′ | HERB + HERB2：先写能过小数据的暴力搜索，再改成一维背包 | 两份代码都能过样例 |
| 第 3 段 | 20–40′ | MISSILE：写 O(n²) 双问，重点检查"不升 / 上升"的等号 | 样例 8 个数输出 6 / 2 |
| 第 4 段 | 40–48′ | 对拍：n ≤ 20 小数据，暴力版与正解版跑同一批随机输入，比对 200 组 | 0 组不一致 |
| 第 5 段 | 48–50′ | 提交前 60 秒自检（见第四节） | 四条全部打勾 |
唯一硬规定：时间盒一到就换下一题，哪怕正解只差一行。
复赛里「三题各拿 60 分」永远胜过「一题 100 分、两题 0 分」。
二、A 卷 · 冲满分路线（三题都要 100）
- HERB：一维数组 + 容量倒序
for (j = T; j >= t; j--)，边界是 j >= t 不是 j > t。
- HERB2：完全背包改正序
for (j = t; j <= T; j++)；价值开 long long。
- MISSILE：第一问最长不升（
h[j] >= h[i]），第二问最长上升（h[j] < h[i]）；答案取 max(d) 不是 d[n]；输入读到 EOF。
- 必做：三题都写暴力版对拍，200 组随机小数据 0 不一致。
三、B 卷 · 保部分分路线（先把能拿的拿稳）
| 题目 | 先拿档位 | 具体动作 | 封顶时间 |
|---|
| HERB | 特判 → 暴力 | 先写 n == 0 || T == 0 → 0；再写"每件选/不选"的递归搜索，n ≤ 20 稳过 | 8′ |
| HERB2 | 正解（直接套） | 与 HERB 只差循环方向，复制后把倒序改正序，10 分钟内必拿 | 8′ |
| MISSILE | 特判 → 暴力 → 正解 | 先 n == 1 → 1 / 1；再 O(2ⁿ) 枚举子序列判合法；最后补 O(n²) | 20′ |
B 卷不要求满分，要求"零爆零"：三题都至少有输出、都不 RE、都不 TLE 到底。
先保证这件事，再回头补正解。
四、提交前 60 秒自检（四条，逐条打勾）
| ✓ | 检查项 | 典型翻车 |
|---|
| ☐ | 循环方向：01 倒序 / 完全正序，逐题念一遍 | 正序写 01 → 答案虚高 |
| ☐ | 答案取法：LIS 取 max(d)，不取 d[n] | 样例过了、大数据错 |
| ☐ | 数据范围：int 会不会溢出，要不要 long long | HERB2 价值累加溢出 |
| ☐ | 文件名与读写：是否 freopen／是否多测清空数组 | 本地对、提交 0 分 |
五、部分分阶梯速查（贴在显示器上）
| 档位 | 预期分 | 做法 | 耗时 |
|---|
| ① 特判档 | 5–10 | n == 0/1、全为 0、已有序等极端情况直接输出 | 2′ |
| ② 暴力档 | 20–30 | 搜索 / 枚举 / 朴素 O(n³)，不优化，保证小数据全对 | 8′ |
| ③ 特殊性质档 | 40–60 | 针对部分测试点的性质单独写一份（如 n ≤ 20、无重复、单调） | 10′ |
| ④ 正解档 | 100 | 完整 DP + 对拍验证 | 20′+ |
六、教练批阅栏（当堂填完，不留到课后）
| 题目 | 得分 | 丢在哪一档 | 具体原因（写现象，不写"粗心"） | 下次动作 |
|---|
| HERB | | | | |
| HERB2 | | | | |
| MISSILE | | | | |
批阅规则：丢分原因必须写成可执行的现象（"LIS 答案取了 d[n]"），
禁止出现"粗心""没看清"这类无法产生下一步动作的词。