洛谷 P1877 [HAOI2012] 音量调节

// P1877 [HAOI2012] 音量调节 —— ★ 这一版就能 AC
//
// 题意：初始音量 beginLevel，最大音量 maxLevel；第 i 首歌之前必须把音量
//       **加上或减去** c[i]，而且**每一步之后**音量都要落在 [0, maxLevel] 里。
//       问最后一首歌的音量最大能是多少；做不到就输出 -1。
//
// ★ 状态是「能不能」而不是「最多是多少」：
//     f[i][j] = 唱完第 i 首歌之前的调整后，音量能不能正好是 j
//     f[i][j] = f[i-1][j - c[i]]  或  f[i-1][j + c[i]]
//   答案就是最大的 j 使 f[n][j] 为真。O(n × maxLevel) = 50 × 1001 —— 五万次，眨眼。
//
// ⚠⚠ 这道题最容易栽的地方是：**照搬 01 背包「压成一维 + 倒序」的招式，当场就错。**
//   理由在解析页第 ③ 步：01 背包的转移只从**更小**的 j 来（单向），
//   所以倒序能保证「读到的还是上一层」；
//   而这道题同时从 j−c（更小）和 j+c（更大）来 —— **双向的转移没有任何一种遍历顺序救得了**。
//   ⇒ 这里老老实实用两个数组滚动：cur 只读 pre，谁也污染不了谁。
//
// ★ 顺带：`0 ≤ j ≤ maxLevel` 这个条件要在**每一层**都成立，不是只在最后
//   （题面写的是「音量不能小于 0 也不能大于 maxLevel」，说的是全程）。

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

int main() {
    int n, begin_, maxLevel;
    if (!(cin >> n >> begin_ >> maxLevel)) return 0;
    vector<int> c(n);
    for (int& x : c) cin >> x;

    vector<char> pre(maxLevel + 1, 0), cur(maxLevel + 1, 0);
    pre[begin_] = 1;
    for (int i = 0; i < n; i++) {
        fill(cur.begin(), cur.end(), 0);
        for (int j = 0; j <= maxLevel; j++) {
            if (!pre[j]) continue;
            if (j - c[i] >= 0) cur[j - c[i]] = 1;          // 调低
            if (j + c[i] <= maxLevel) cur[j + c[i]] = 1;   // 调高
        }
        pre.swap(cur);                                     // ★ 滚动：cur 只读 pre
    }

    int ans = -1;
    for (int j = maxLevel; j >= 0; j--)
        if (pre[j]) { ans = j; break; }
    cout << ans << "\n";
    return 0;
}

// P1877 错法一：照搬 01 背包 —— 压成一维、倒着写
//
// 「01 背包一维要倒序」这句话背得很熟，于是顺手就写成了这样。
//
// ⚠⚠ 它在这道题上**不成立**，而理由很干净：
//   01 背包的转移是 f[j] ← f[j-w]，**只从更小的 j 来**（单向），
//   所以倒序能保证「读到的 f[j-w] 还是上一层的」。
//   这道题的转移是 f[j] ← f[j-c] **或** f[j+c] —— 一个在左、一个在右。
//   ⇒ 倒序保住了左边（j-c 还没被本层改），却**保不住右边**（j+c 已经被本层改过了）。
//
// ⚠⚠ 草稿里我写的是「它认为可达的音量**只多不少**，所以答案恒 ≥ 正解」——
//   **实测把这句话打回来了**：300 轮里它的可达集包含正解的只有 **248 轮**，
//   答案偏大 88 轮、**偏小 2 轮**。
//   ⇒ 就地覆盖既会**凭空造出**状态（同一首歌被用了不止一次），
//     也会**弄丢**合法状态（右边那格在被读到之前已经被本层抹成 0 了）。
//
// ★ 最小反例只要**一首歌**：`maxLevel = 1`，`begin = 1`，`c = [1]`
//   ⇒ 正解是 0（调低一格），而它输出 **-1**。
//   （j=1 先被算成 0，轮到 j=0 去读 f[1] 时，读到的已经是本层刚写的那个 0。）

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

int main() {
    int n, begin_, maxLevel;
    if (!(cin >> n >> begin_ >> maxLevel)) return 0;
    vector<int> c(n);
    for (int& x : c) cin >> x;

    vector<char> f(maxLevel + 1, 0);
    f[begin_] = 1;
    for (int i = 0; i < n; i++)
        for (int j = maxLevel; j >= 0; j--) {              // ⚠ 倒序，就地覆盖
            char ok = 0;
            if (j - c[i] >= 0 && f[j - c[i]]) ok = 1;      // 左边：倒序时它还是上一层 ✓
            if (j + c[i] <= maxLevel && f[j + c[i]]) ok = 1;  // ⚠ 右边：本层已经改过了
            f[j] = ok;
        }

    int ans = -1;
    for (int j = maxLevel; j >= 0; j--)
        if (f[j]) { ans = j; break; }
    cout << ans << "\n";
    return 0;
}