题目描述

题目传送门

思路

有显然的三维 dp。

fi,j,kf_{i,j,k} 表示前 ii 个朋友用了 jj 个哞尼和 kk 个冰激凌甜筒能得到的最大价值。

那么有:

fi,j,k=maxw>ci,w×xi>k{fi1,j,k,fi1,jci+w,kw×xi+pi}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\}

时间复杂度 Θ(n3)\Theta(n ^ 3),空间复杂度可以用滚动数组优化至 Θ(n2)\Theta(n ^ 2)

没有前途的 75pts。

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

fi,jf_{i,j} 表示前 ii 个用了 jj 个哞尼的最大价值。这个 dp 很简单,时间复杂度 Θ(n2)\Theta(n^2)

接下来考虑上冰淇淋,设 fi,jf_{i,j} 表示前 ii 个用了 jj 个冰淇淋的最大价值。

如果我们确定了要选择几个朋友,现在手上有 bb 个冰激凌,那我们完全可以完全收买这个朋友后再去收买其他朋友,这里的转移可以利用 ff。时间复杂度 Θ(n2)\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;
}