526互联

abc060d <dp, 背包>

发布时间 2023-06-25 09:37:22作者: O2iginal

D - Simple Knapsack

// https://atcoder.jp/contests/abc060/tasks/arc073_b
// 背包问题
// 特别在于, 背包体积极大; 但是每个物品间的体积都限制在 w[1] ~ w[1]+3 的小范围内
// 因而可以将所有物品减去一个共同的 w[1] 的体积偏移, 这样背包体积就可以限制在 3*n 的范围内了
// 注意需要添加 '选择了几个物品' 维度, 否则不能计算出共减去了多少体积偏移

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 110, M = 500;
LL w[N], v[N];
LL dp[N][M];

void solv()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> w[i] >> v[i];
    LL base = w[1];

    for (int i = 1; i <= n; i ++)  // 考虑前i个物品
    {
        LL wi = w[i] - base, vi = v[i];
        for (int j = i; j >= 1; j --)  // 前i个物品中选j个
            for (int k = M-1; k >= wi; k --)  // 体积不超过k (减去偏移之后)
                dp[j][k] = max(dp[j][k], dp[j-1][k-wi] + vi);
    }

    LL ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        LL wi = m - base * i;
        if (wi >= M) wi = M - 1;  // 注意这里控制一下范围, 否则 RE ~
        if (wi < 0) break;

        ans = max(ans, dp[i][wi]);
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}