[USACO22DEC] Bribing Friends G

题目描述

题目传送门

思路

有显然的三维 dp。

设 $f_{i,j,k}$ 表示前 $i$ 个朋友用了 $j$ 个哞尼和 $k$ 个冰激凌甜筒能得到的最大价值。

那么有：

$$f_{i,j,k} = \max_{w > c_i,w \times x_i > k}\{f_{i-1,j,k}, f_{i-1,j-c_i+w,k-w\times x_i} + p_i\}$$

时间复杂度 $\Theta(n ^ 3)$，空间复杂度可以用滚动数组优化至 $\Theta(n ^ 2)$。

没有前途的 75pts。

考虑先对 $x_i$ 从大到小排个序，然后对冰淇淋和哞尼分别进行 dp。

设 $f_{i,j}$ 表示前 $i$ 个用了 $j$ 个哞尼的最大价值。这个 dp 很简单，时间复杂度 $\Theta(n^2)$。

接下来考虑上冰淇淋，设 $f_{i,j}$ 表示前 $i$ 个用了 $j$ 个冰淇淋的最大价值。

如果我们确定了要选择几个朋友，现在手上有 $b$ 个冰激凌，那我们完全可以完全收买这个朋友后再去收买其他朋友，这里的转移可以利用 $f$。时间复杂度 $\Theta(n^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2010;

int f[3][MAXN][MAXN];
int n, A, B, Ans;

struct _ {
	int p, c, x;
} o[MAXN];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++)
		cin >> o[i].p >> o[i].c >> o[i].x;
	sort(o + 1, o + 1 + n, [](_ a, _ b) {
		return a.x < b.x;
	});
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= A; j++) f[1][i][j] = f[1][i + 1][j];
		for (int j = o[i].c; j <= A; j++) f[1][i][j] = max(f[1][i][j], f[1][i + 1][j - o[i].c] + o[i].p);
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= B; j++) {
			f[2][i][j] = f[2][i + 1][j];
			if (o[i].c <= j / o[i].x) f[2][i][j] = max(f[2][i][j], f[2][i + 1][j - o[i].c * o[i].x] + o[i].p);
			else f[2][i][j] = max(f[2][i][j], f[1][i + 1][A - (o[i].c - j / o[i].x)] + o[i].p);
			Ans = max(Ans, f[2][i][j]);
		}
	}
	cout << Ans << endl;
	return 0;
}