AT_abc_373F Solution

\(O(n^3)\) 的 dp 很容易想到，枚举重量，枚举物品，枚举物品选择数量，我们考虑把它优化到 \(O(n^2)\) ，显然重量与物品的枚举不能避免，所以我们考虑省去数量的枚举。
记 \(num_{i,j}\) 表示 总质量为 i 价值达到最大时，j 选择了多少个，对于当前枚举的重量 i ,我们枚举选择第 j 个物品，然后求一下 \(\max_1^n f_{i-w_j}+v_j-2num_{i-w_j,j}-1\) 记一下最大值对应的物品是哪个，用最大值更新 \(f_i\) ，顺便再用 \(num_{i-w_maxid,j}\) 更新一下 \(num_{i,j}\) 即可。
code

signed Main(){
  n = read(), W = read();
  for (Yc i = 1; i <= n; i++) w[i] = read(), v[i] = read();
  Yc ans = 0;
  for (Yc i = 1; i <= W; i++) {
    Yc maxv = 0, maxid;
    for (Yc j = 1; j <= n; j++) {
      if (w[j] > i) continue;
      if (f[i - w[j]] + v[j] - 2ll * num[i - w[j]][j] - 1ll > maxv) {
        maxv = f[i - w[j]] + v[j] - 2ll * num[i - w[j]][j] - 1ll;
        maxid = j;
      }
    }
    if (!maxv) continue;
    f[i] = maxv;
    for (Yc j = 1; j <= n; j++) num[i][j] = num[i - w[maxid]][j];
    num[i][maxid]++;
    ans = max(ans, f[i]);
  }
  //   for (Yc i = 1; i <= W; i++, ps(""))
  //     for (Yc j = 1; j <= n; j++) write(num[i][j]), pc(' ');
  write(ans), ps("");

  return 0;
}