2585. 获得分数的方法数

发表于 分类于 阅读次数： Waline： 本文字数： 1.8k 阅读时长 ≈ 6 分钟

考点

  • 多重背包
  • 前缀和
  • 滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int waysToReachTarget(int target, vector<vector<int>>& types) {
    const int mod = 1e9 + 7;
    long long f[2][1005];
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    int n = types.size();
    for (int i = 1; i <= n; ++i) {
      int c = types[i - 1][0], w = types[i - 1][1];
      // 遍历j = r + k * w
      for (int r = 0; r < w; ++r) {
        // 滑动窗口的和
        long long sum = 0;
        for (int j = r, k = 0; j <= target; j += w, k++) {
          sum = (sum + f[i-1 & 1][j]) % mod;
          if (k >= c + 1)
            sum = (sum - f[i-1 & 1][r + (k - c - 1) * w] + mod) % mod;
          f[i & 1][j] = sum;
        }
      }
    }
    return f[n & 1][target];
  }
};

思路

多重背包的精髓题，必刷

但题意描述不清，这是最恶心的地方！！

它实际上想表达的意思是，你不能像经典的多重背包一样：

  • 把每个同类型的物品单独拆成一个个不同的物品进行01背包
  • 或者二进制拆分再进行01背包

所以如果你写出这样的代码，那肯定是错的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int waysToReachTarget(int target, vector<vector<int>>& types) {
    const int mod = 1e9 + 7;
    // f[i][j]: 考虑前i个，能满足j容量的方案数
    long long f[1005];
    int n = types.size();
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
      int w = types[i - 1][1], c = types[i - 1][0];
      for (int k = 0; k < c; ++k) {
        for (int j = target; j >= 0; --j) {
          if (j >= w) f[j] = (f[j] + f[j - w]) % mod;
        }
      }
    }
    return f[target];
  }
};

多重背包优化学习

绝对能理解你为啥会觉得“单调队列优化多重背包”很劝退——其实它并不玄学，核心只做了两件事：

  1. 把容量（分数）按重量 \(w\) 的同余类分组：\(j \equiv r \pmod w\)。
  2. 在每个同余类的“一条等差数列”上，把「选 0..c 个」这种滑动窗口的区间操作，用前缀和（求和问题）或单调队列（取最大值问题）做成 \(O(1)\) 更新。

1. 经典多重背包的两种转移

设某一类物品（题目）参数为：最多选 \(c\) 个，重量（得分）\(w\)，（可选）价值 \(v\)。

  • 计数型（求方案数） \[ \text{new}[j] \;=\; \sum_{t=0}^{\min(c, \lfloor j/w \rfloor)} \text{old}[j - t\cdot w] \] ——把上一层的若干位置加起来（区间求和）。

  • 最大值型（求最大价值） \[ \text{new}[j] \;=\; \max_{0\le t\le c,\;t w\le j}\;\bigl(\text{old}[j - t w] + t\cdot v\bigr) \] ——在上一层的若干位置里取区间最大，并加上线性项 \(t\cdot v\)。

2. 同余类分组：把二维卷成一维“等差序列”

固定某一类 \((c,w,v)\)，对容量 \(j\) 按 \(w\) 分组： 令 \(j = r + k w\)（\(r\in[0,w-1]\)，\(k\ge 0\)）。

把上一层数组 \(\text{old}[\,]\) 在该组里采样，得到一条序列： \[ g_k \;=\; \text{old}[r + k w],\quad k=0,1,2,\dots \] 那么两种转移在这条序列上的样子分别是：

  • 计数型（求和） \[ \text{new}[r + k w] \;=\; \sum_{t=0}^{c} g_{k - t}\quad (\text{越界忽略}) \] 这就是对 \(g\) 做一个长度 \(c+1\) 的滑动窗口求和。

  • 最大值型（取最大） 先把线性项“搬过去”： 令 \(h_t = g_t - t\cdot v = \text{old}[r + t w] - t v\)， 则 \[ \text{new}[r + k w] \;=\; k v + \max_{t\in[k-c,\,k]} h_t \] ——这是对 \(h\) 做长度 \(c+1\) 的滑动窗口最大值，非常适合用单调队列维护。

3. 草图（ASCII）

3.1 计数型 = 滑动窗口求和

以某个同余类 \(r\) 为例，\(g_k=\text{old}[r+k w]\)：

1
2
3
4
5
6
7
8
9
10
11
12
k:     0     1     2     3     4     5     6   ...
g[k]: [g0] [g1] [g2] [g3] [g4] [g5] [g6] ...

窗口大小 = c+1

new[r + 0*w] = g0
new[r + 1*w] = g0 + g1
new[r + 2*w] = g0 + g1 + g2
...
每往右移动一步，就：
    + 进一个 g[k]
    - 出一个 g[k-(c+1)]（如果存在）

直观上就是一个“盒子（窗口）”在这条数列上向右滑，盒子里元素的和就是答案。

3.2 最大值型 = 滑动窗口最大值（单调队列）

对 \(h_t = g_t - t v\)：

1
2
3
4
5
6
7
8
9
k:       ...  k-(c+1)   ...   k-2   k-1   k
h[k]:         [  ·   ]        [...] [...] [...]

窗口 = 最近 (c+1) 个 h
单调队列里保存“可能成为窗口最大值”的下标，且队内 h[·] 单调不增
- 入队：把 <= 新值的尾巴弹掉，再把新下标放进来
- 出队：弹掉已经滑出窗口左边界的下标
- 队首：就是当前窗口最大值的下标 idx
答案：new[r + k*w] = k*v + h[idx]

4. 计数型（方案数）的滑动窗口代码（\(O(n\cdot \text{target})\)）

这是你这题应该用的版本：不需要单调队列，只要窗口和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 计数型：对每一类 (c, w) 做 w 个同余类的滑动窗口求和
int waysToReachTarget(int target, vector<vector<int>>& types) {
    const int MOD = 1'000'000'007;
    vector<int> dp(target + 1, 0);
    dp[0] = 1;

    for (auto &t : types) {
        int c = t[0], w = t[1];
        vector<int> old = dp; // 锁定上一层，避免“自我污染”
        for (int r = 0; r < w; ++r) {
            long long window = 0;
            // 沿着 j = r + k*w 递增遍历
            for (int j = r, k = 0; j <= target; j += w, ++k) {
                // 入窗：old[j]
                window += old[j];
                if (window >= MOD) window -= MOD;
                // 出窗：old[j - (c+1)*w]
                int outj = j - (c + 1) * w;
                if (outj >= 0) {
                    window -= old[outj];
                    if (window < 0) window += MOD;
                }
                dp[j] = (int)window; // 当前窗口和
            }
        }
    }
    return dp[target];
}

和01背包的易错点 01背包的做法是，“把这一类拆成 \(c\) 个 0/1 物品，且用同一个数组逆序 j 转移”——这会把同类的不可区分物品当成可区分物品，在某些容量上重复计数。用“上一层 old → 下一层 dp”的分层 + 余数类滑窗，就不会互相污染，也不会重计。

5. 最大值型（价值最大）用“单调队列”维护窗口最大

如果某题是要最大总价值，每件物品价值 \(v\)，转移是： \[ \text{new}[j] = \max_{0\le t\le c,\ t w\le j} \text{old}[j - t w] + t v \] 化到同余类后： \[ \text{new}[r + k w] = k v + \max_{t\in[k-c,\,k]} \bigl(\text{old}[r + t w] - t v\bigr) \] 对 \(h_t = \text{old}[r + t w] - t v\) 做固定长度 \(c+1\) 的滑动窗口最大值，用单调队列（deque）维护即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 最大值型模板（演示用）：dp 求最大价值；无解处设为 -INF
int boundedKnapsackMaxValue(int target, vector<array<int,3>>& items) {
    // items: {count c, weight w, value v}
    const int NEG = -1e9; // 根据题目调整
    vector<int> dp(target + 1, NEG), ndp(target + 1, NEG);
    dp[0] = 0;

    for (auto &it : items) {
        int c = it[0], w = it[1], v = it[2];
        ndp = dp; // 注意：有些题允许“不用这一类”，所以先拷过去

        for (int r = 0; r < w; ++r) {
            deque<int> q; // 存 t 的下标，维护 h[t] 单调不增
            // k 对应 j = r + k*w
            for (int k = 0, j = r; j <= target; j += w, ++k) {
                // 计算 h[k] = dp[r + k*w] - k*v
                long long hk = (dp[j] == NEG ? (long long)-4e18 : (long long)dp[j] - 1LL*k*v);

                // 入队：把队尾 <= hk 的弹掉，保持单调
                while (!q.empty()) {
                    int t = q.back();
                    long long ht = (dp[r + t*w] == NEG ? (long long)-4e18 : (long long)dp[r + t*w] - 1LL*t*v);
                    if (ht >= hk) break;
                    q.pop_back();
                }
                q.push_back(k);

                // 出队：窗口左边界 k-c
                while (!q.empty() && q.front() < k - c) q.pop_front();

                // 用队首计算 new
                if (!q.empty()) {
                    int t = q.front();
                    long long ht = (dp[r + t*w] == NEG ? (long long)-4e18 : (long long)dp[r + t*w] - 1LL*t*v);
                    long long cand = 1LL*k*v + ht;
                    if (cand > ndp[j]) ndp[j] = (int)cand;
                }
            }
        }
        dp.swap(ndp);
    }
    return dp[target];
}

总结

  • 计数：窗口求和 → 用前缀和/滑窗
  • 最大值：窗口取最大 → 用单调队列维护窗口最大值。
  • 两者的统一钥匙：同余类分组（按 \(w\) 把一维拉成若干条等差序列）。