Bribing Friends (USACO Gold December 2022)

两种资源的0-1背包，一种资源可以按比例替换另一种，求最大收益。

如果用最简单定义的DP来解（考虑前 $i$ 个朋友，剩下多少个moonies和cones），复杂度是 $O(n^4)$ ，因为有 $n^3$ 个状态，生成一个状态需要 $O(n)$ 循环， $n=2000$ ，所以会TLE。

观察题目，可以看到ice cream cones具有单调性，应该先用 $x[i]$ 值小的friend，因为交换得到的钱更多。所以将friends按 $x[i]$ 从小到大排序。

继续这个想法，排序完成之后，我们应该优先使用cones，直到全部用光（可能剩下不能兑换的少数几个），然后再开始用moonies（这个时候基本回到标准0-1背包了）。

所以我们可以构造 $\text{dp}[i][j]$ , 在前 $i$ 个朋友中选择，而且剩下 $j$ 个moonies+cones的时候，能达到的最大popularity。

初始状态是 $\text{dp}[0][A+B] = 0$ 。

状态转移就从 $\text{dp}[i-1][j]$ 出发，有四种情况：

不选择 $i$ 这头牛: $\text{dp}[i][j] = \text{dp}[i-1][j]$ .
有足够的cones可以买cow $i$ 的所有moonies: $\text{dp}[i][j - c \cdot x] = \text{dp}[i-1][j] + p$
没有cones了，直接花moonies: $\text{dp}[i][\min(j,A)-c] = \text{dp}[i-1][j] + p$ .
有部分的cones可以买cow $i$ 的moonies: 见下面代码。

这个题目是利用数据的结构，对DP降维的技巧。此题的关键，是要搞明白题目中的单调性，理解到先用cones是更优的，然后把两种资源合并起来，让计算过程减少 $\mathcal{O}(n^2)$ 复杂度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,A,B;
int dp[2005][4005];
struct C {
    int p, c, x;
    bool operator<(const C &b) const {
        return x < b.x;
    }
};
vector<C> cows;
 
int main() {
    scanf("%d %d %d", &n, &A, &B);
    for (int i = 0; i < n; i++) {
        int p,c,x;
        scanf("%d %d %d", &p, &c, &x);
        cows.push_back({p, c, x});
    }
    sort(cows.begin(), cows.end());          // sort by X[i] (# of cones)
 
    fill(dp[0], dp[0]+A+B, -1);
    dp[0][A+B] = 0;
    for (int i = 1; i <= n; i++) {           // consider cow i-1
        C c = cows[i-1];
        for (int j = 0; j <= A+B; j++)      // do not choose cow i-1
            dp[i][j] = dp[i-1][j];
        for (int j = 0; j <= A+B; j++) {
            if (dp[i-1][j] >= 0) {          // choose cow i-1
                if (j >= A + c.x) {         // could use cones
                    if (j-A >= c.c*c.x) {   // all cones
                        dp[i][j-c.c*c.x] = max(dp[i][j-c.c*c.x], dp[i-1][j] + c.p);
                    } else {                // partial cones
                        int mooney = c.c-(j-A)/c.x;
                        dp[i][A-mooney] = max(dp[i][A-mooney], dp[i-1][j] + c.p);
                    }
                } else if (min(A, j) >= c.c) {   // no cones
                    int m = min(A, j);
                    dp[i][m-c.c] = max(dp[i][m-c.c], dp[i-1][j] + c.p);
                }
            }
        }
    }
    int ans = *max_element(dp[n], dp[n]+A+B+1);
    printf("%d", ans);
    return 0;
}