题解：P4912 帕秋莉的魔法

huangjiayi2024 · 2026-11-10 14:12:55 · 题解

题目简化

给定一个容积为 m 的包，有 n 个物品，每个物品只能选一次，对于第 i 个物品，其体积为 a_i，价值为 b_i，且如果在选了第 i 个物品后，立马再次选择物品 j，可额外获得价值 w_{i,j}，求把包装满的最大价值。

题目分析

这道题很显然是个背包，但是貌似多加了个 w_{i,j}，那不就是在转移的时候价值多加个 w 就行了吗，因为 n 的值特别小，n \le 500，那就直接 O(n^2m) 时间转移，都不用进行任何优化。

但是值得注意的是，题目说的是 \lvert a_i \rvert \le 50 而不是 0 \le a_i \le 50，所以 a_i 可能为负数，那不就是弄个偏移量嘛。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 50 + 10, p = 2501; // 偏移量
int n, m, a[N], b[N], dp[N][p * 2 + 10], w[N][N]; // 不要开小了
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> w[j][i];
    memset(dp, -0x3f, sizeof dp);
    dp[0][p] = 0; // 不要初始化错了
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 5001; j++) 
            for (int k = 0; k < i; k++)
                if ((j - a[i]) >= 0 && (j - a[i]) <= 5001) // 防止越界
                    dp[i][j] = max(dp[i][j], dp[k][j - a[i]] + b[i] + w[i][k]); // 转移
    } int ans = dp[0][0];
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i][m + p]); // 这里不要忘
    if (ans <= dp[0][0] / 2) cout << -1; // -1 也不要忘了输出
    else cout << ans;
    return 0;
}