P8903

· · 题解

[USACO22DEC] Bribing Friends G

题目描述

Bessie 想要观看纪录片：奶牛基因组学，但她不想一个人去。不幸的是，她的朋友们没有足够的热情和她一起去！于是，Bessie 需要贿赂她的朋友们陪她去电影院。她的贿赂武器库中有两种工具：哞尼和冰激凌甜筒。

Bessie 有 N(1 \le N \le 2000) 个朋友。然而，并非所有的朋友都是生而平等的！朋友 i 有受欢迎度 P_i(1 \le P_i \le 2000)，Bessie 想最大化陪她的朋友们的受欢迎度之和。朋友 i 只有当 Bessie 给了她 C_i(1 \le C_i \le 2000) 哞尼才愿意陪她。如果 Bessie 给她 X_i(1 \le X_i \le 2000) 个冰激凌甜筒，她还可以给 Bessie 1 哞尼的折扣。Bessie 可以从朋友那里得到任意整数数量的折扣，只要这些折扣不会使得朋友倒给她哞尼。

Bessie 有 A 哞尼和 B 个冰激凌甜筒可供使用（0 \le A,B \le 2000）。请帮助她求出如果她以最优方案花费她的哞尼和冰激凌甜筒，她可以达到的最大受欢迎度之和。

做法

既然每个朋友每次都只给 1 元钱的折扣，那我只要给要冰激凌最少的那个不就行了。

很可惜，并不行。就像捆绑销售，朋友只是给 Bessie 折扣，而不是直接给她钱，所以给要冰激凌最少的那个不一定是最优的。

但这为我们打开了一个思路：假设我们已经确定了最后要选哪几位朋友，那么优先给需要冰激凌最少的那位是最划算的。

所以我们先将朋友按 X_i 升序排序，然后倒着做一遍01背包，就可以知道如果现在有 a 个哞尼，从后往前找到第 i 个朋友，最大的受欢迎度是多少。

然后再从后往前进行一次dp，枚举有 b 个冰激凌，最大的受欢迎度是多少。

假设 b 个冰激凌完全能收买这个朋友，那么我们还剩 b' 个冰激凌继续去收买先前枚举过的朋友。假设 b 个冰激凌不能完全收买这个朋友，那么之前枚举过的朋友也一定不能再用冰激凌收买，这时就利用第一次的dp，得到最大的受欢迎度是多少。

代码

不太理解的部分可以看代码。


const ll N=205;
const ll M=2005;
const ll inf=0x3f3f3f3f;
ll n,m,k,ans;
struct node{
    ll a,c,x;
}a[M];
ll dp[M][M],f[M][M];
inline bool cmp(node a,node b){
    return a.x<b.x;
}
inline void pre_solve(){
    UF(i,n,1){
        F(j,0,m) dp[i][j]=dp[i+1][j];
        F(j,a[i].c,m) dp[i][j]=max(dp[i][j],dp[i+1][j-a[i].c]+a[i].a);
    }
}
int main(){
    n=read();m=read();k=read();
    F(i,1,n) a[i].a=read(),a[i].c=read(),a[i].x=read();
    sort(a+1,a+n+1,cmp);
    pre_solve();
    UF(i,n,1){
        F(j,0,k){
            f[i][j]=f[i+1][j];
            ll num=min(a[i].c,j/a[i].x);
            ll lst=j-num*a[i].x;
            if(num==a[i].c) f[i][j]=max(f[i][j],f[i+1][lst]+a[i].a);
            else f[i][j]=max(f[i][j],dp[i+1][m-(a[i].c-num)]+a[i].a);
            ans=max(ans,f[i][j]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}