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

· · 题解

首先我们会有一部分物品两个人都买到。我们把这些物品扔到最前面。

而对于剩下的物品，我们会让一部分只能 A 买到，一部分只能 B 买到。对于这部分，按 c_i 降序放置一定是不劣的。

考虑枚举 s 表示两个人都买到的物品总价。将所有物品按 c_i 降序排序。然后设状态 f_{i, p, j, k} 表示考虑前 i 个物品，两个人都买的总共是 p，只能 A 买到的已经买了 j，只能 B 买到的已经买了 k。

转移时，我们决策一个物品到底是什么情况。

这样直接暴力 DP 是五次方的。

这样 DP 不够优秀的主要原因是外层枚举了 s。

考虑一开始就决定每个人分别都选了多少。重新考虑状态 f_{i, s, j, k} 表示考虑前 i 个物品，当前两个人都选的部分还有 s 的债要还，只能 A 买的部分还有 j 的债要还，只能 B 买的部分还有 k 的债要还。

初始状态是 f_{0, s, a-s, b-s} = 0，其它的设成 -\infty 就行了。

这样转移时“剩下的空间”这个限制就可以直接被 j 或 k 表示了。可以直接 DP 做到 O(n V^3)。

最后对所有 f_{n, 0, j, k} 取个 \max，就是答案了。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 200 + 5;

int f[2][N][N][N], ans, n, a, b, c[N], u[N], v[N], q[N];

inline bool cmp(int x, int y)
{
    return c[x] > c[y];
}

signed main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> a >> b;

    for(int i = 1; i <= n; i++)
        cin >> c[i] >> u[i] >> v[i], q[i] = i;
    sort(q + 1, q + n + 1, cmp);

    memset(f, -0x3f, sizeof f);
    for(int s = 0; s <= min(a, b); s++)
        f[0][s][a - s][b - s] = 0;
    for(int i = 1; i <= n; i++)
    {
        int C = c[q[i]], U = u[q[i]], V = v[q[i]];

        for(int p = 0; p <= min(a, b); p++)
        for(int j = 0; j <= a; j++)
        for(int k = 0; k <= b; k++)
            f[i & 1][p][j][k] = f[(i - 1) & 1][p][j][k];

        for(int p = C; p <= min(a, b); p++)
        for(int j = 0; j <= a; j++)
        for(int k = 0; k <= b; k++)
            f[i & 1][p - C][j][k] = max(f[i & 1][p - C][j][k], f[(i - 1) & 1][p][j][k] + U + V);

        for(int p = 0; p <= min(a, b); p++)
        for(int j = 0; j <= a; j++)
        for(int k = 0; k <= b; k++)
        {
            if(f[(i - 1) & 1][p][j][k] < 0) continue;
            if(j >= C && k < C)
            {
                f[i & 1][p][j - C][k] = max(f[i & 1][p][j - C][k], f[(i - 1) & 1][p][j][k] + U);
            }
            if(k >= C && j < C)
            {
                f[i & 1][p][j][k - C] = max(f[i & 1][p][j][k - C], f[(i - 1) & 1][p][j][k] + V);
            }           
        }
    }       
    for(int j = 0; j <= a; j++)
    for(int k = 0; k <= b; k++)
        ans = max(ans, f[n & 1][0][j][k]);
    cout << ans << '\n';    
    return 0;
}