题解：P17544 [JAG 2026 Summer Camp #2] Two Greedy Customers

stripe_python · 2026-10-21 16:15:10 · 题解

原问题显然强于 01 背包，考虑刻画性质后 DP。

我们提前钦定每个物品被 AB 双买，或 A 单买，或 B 单买，或 AB 都不买。则最终序列中 AB 类物品放在最前面，然后是单买物品，最后是扔掉的物品不劣。

设两人买完 AB 类物品后还剩 a_0 和 b_0 元，不妨设 a_0 \ge b_0，则 A 物品必须要 b_0<c_i \le a_0，B 物品必须 a_1<c_i \le b_0，其中 a_1 是 A 买完所有 A 物品后的余额。将 A 部分按 c_i 降序排列，这样 A 物品使得 a_0 不断减少，到 B 物品时 A 就买不起了，而 B 部分可以随便排列。

我们不必检查被扔掉的物品，因为这些物品如果能买上，这个方案一定是更劣的。

我们枚举 AB 类物品的总价格。将物品按价格降序排序后逐个加入，设计 DP 为 f_{i,j,k,p} 表示考虑前 i 个物品，A 手上有 j 元，B 手上有 k 元，待匹配的 AB 类物品还剩 p 元余额时的最大收益，转移是简单的。

可以发现不需要每次枚举都 DP。钦定 i 元 AB 物品时，直接赋值 f_{0,a-i,b-i,i}=0，其余位置 -\infty。做完 DP 后强制 p=0 提取答案。

对 i 维度滚动数组。时间 O(nV^3) 跑不满，可以通过。

const int N = 125;
const i64 inf = 1e18;
int n, a, b;
i64 f[2][N][N][N];
struct node {
    int c, w1, w2;
} x[205];

void _main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) 
        cin >> x[i].c >> x[i].w1 >> x[i].w2;
    sort(x + 1, x + n + 1, [](const node& a, const node& b) {
        return a.c > b.c;
    });
    memset(f, 0xcf, sizeof(f));
    for (int i = 0; i <= min(a, b); i++) f[0][a-i][b-i][i] = 0;
    for (int i = 1, st = 1; i <= n; i++, st ^= 1) {
        int v = x[i].c;
        memcpy(f[st], f[st^1], sizeof(f[st]));
        for (int j = 0; j <= a; j++)
            for (int k = 0; k <= b; k++)
                for (int p = 0; j + p <= a && k + p <= b; p++) {
                    if (p >= v) chkmax(f[st][j][k][p-v], f[st^1][j][k][p] + x[i].w1 + x[i].w2);
                    if (j >= v && k < v) chkmax(f[st][j-v][k][p], f[st^1][j][k][p] + x[i].w1);
                    if (k >= v && j < v) chkmax(f[st][j][k-v][p], f[st^1][j][k][p] + x[i].w2);
                }     
    }
    i64 res = 0;
    for (int j = 0; j <= a; j++)
        for (int k = 0; k <= b; k++)
            for (int p = 0; j + p <= a && k + p <= b; p++) 
                chkmax(res, f[n&1][j][k][p]);
    cout << res;
}