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

· · 题解

模拟赛 T2，依旧死于 dp。

考虑每种物品的依次购买情况，发现最优情况一定存在如下的情况：

可以先将所有物品从小到大排序。

因此对于一个物品，根据 Alice 和 Bob 是否购买，存在四种决策。

发现对于一个物品，如果要强令 A 不买这个，设当前有 x 钱，这个物品花费为 c。由于在未来可能还会有两个人都买的东西，假设这些花费之和是 R，那么需要满足 A-x-R<c，及 R \ge A-x-c+1。

设 f(i,j,k) 表示 A,B 分别已经花费 i,j 元，并未来还需要共同买至少 k 元的商品。

转移：

复杂度最坏应该是 O(nAB \min(A,B))，但是转移时由于 d \le \min(A-i,B-j)，所以实际复杂度比这个小很多。

状态还是太巧妙了，够我学一辈子了。

#include <bits/stdc++.h>
using namespace std;
const int N=205;
#define ll long long
int n,A,B;
struct node{
    int c,u,v;
    bool operator < (const node &o) const{
        return c>o.c;
    }
}a[N];
ll f[N][N][N];
int main(){
    scanf("%d%d%d",&n,&A,&B);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i].c,&a[i].u,&a[i].v);
    sort(a+1,a+n+1);
    const ll inf=-(1ll<<60);
    for(int i=0;i<=200;++i) for(int j=0;j<=200;++j) for(int k=0;k<=204;++k){
        f[i][j][k]=inf;
    }
    f[0][0][0]=0; 
    for(int _=1;_<=n;++_){
        int c=a[_].c,x=a[_].u,y=a[_].v;
        for(int i=A;i>=0;i--) for(int j=B;j>=0;j--){
            int maxd=min(A-i,B-j);
            for(int d=0;d<=maxd;++d){
                if(f[i][j][d]==inf) continue;
                if(i+c<=A && j+c<=B){
                    int d_=max(d-c,0);
                    ll &to=f[i+c][j+c][d_];
                    to=max(to,f[i][j][d]+x+y);
                }
                if(i+c<=A){
                    int d_=max(B-j-c+1,d);
                    ll &to=f[i+c][j][d_];
                    to=max(to,f[i][j][d]+x);
                }
                if(j+c<=B){
                    int d_=max(A-i-c+1,d);
                    ll &to=f[i][j+c][d_];
                    to=max(to,f[i][j][d]+y);
                }
            }
        }
    }
    ll res=0;
    for(int i=0;i<=A;++i) for(int j=0;j<=B;++j){
        res=max(res,f[i][j][0]);
    }
    printf("%lld\n",res);
}