题目传送门
题目描述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 行包含三个整数 \(N\)，\(A\) 和 \(B\)，分别表示 Bessie 拥有的朋友的数量，哞尼的数量和冰激凌甜筒的数量。
以下 \(N\) 行每行包含三个整数 \(P_i\)，\(C_i\) 和 \(X_i\)，表示受欢迎度（\(P_i\)），贿赂朋友 \(i\) 陪 Bessie 所需要的哞尼（\(C_i\)），以及从朋友 \(i\) 处获得 \(1\) 哞尼的折扣所需要的冰激凌甜筒的数量（\(X_i\)）。
输出格式输出陪 Bessie 的朋友们的最大受欢迎度之和，假设她以最优方案花费她的哞尼和冰激凌甜筒。
样例 #1样例输入 #13 10 85 5 46 7 310 6 315Bessie 可以将 \(4\) 哞尼和 \(4\) 个冰激凌甜筒给奶牛 \(1\)，将 \(6\) 哞尼和 \(3\) 个冰激凌甜筒给奶牛 \(3\)，这样奶牛 \(1\) 和 \(3\) 就可以陪她，得到 \(5+10=15\) 的受欢迎度。
测试点性质测试点 \(2-4\) 满足 \(N \le 5\) 以及 \(C_i=1\)。测试点 \(5-7\) 满足 \(B=0\)。测试点 \(8-10\) 满足 \(N,A,B,P_i,C_i,X_i \le 50\)。测试点 \(11-15\) 满足 \(N,A,B,P_i,C_i,X_i \le 200\)。测试点 \(16-20\) 没有额外限制。感觉洛谷和oj上的翻译不太一样啊。
题目大意现在有 \(N\) 个人，每个人有一个欢迎程度 \(P\) ，代价 \(C\) ，代价减少 \(1\) 需要冰淇淋 \(X\) ，现在有 \(A\) 元钱和 \(B\) 个冰淇淋，求能达到的最大欢迎程度。
考试时想到了 \(O(n^4)\) 的朴素做法，类似背包 ，拿了60分
#include #define fu(x, y, z) for (int x = y; x <= z; x++)#define LL long longusing namespace std;const int N = 205;LL f[N][N][N], ans;int n, a, b, p[N], c[N], x[N];int main() { scanf("%d%d%d", &n, &a, &b); fu(i, 1, n) { scanf("%d%d%d", &p[i], &c[i], &x[i]); } LL ct; fu(i, 0, a) { fu(j, 0, b) { fu(k, 1, n) { for (int l = 0; l <= c[k] && j >= l * x[k]; l++) { ct = c[k] - l; if (i < ct) continue; f[i][j][k] = max(f[i - ct][j - l * x[k]][k - 1] + p[k], f[i][j][k]); } f[i][j][k] = max(f[i][j][k - 1], f[i][j][k]); ans = max(ans, f[i][j][k]); } } } printf("%lld", ans); // printf ("%lld" , f[a][b][n]); return 0;} 正解是贪心：
先把朋友按照 \(X\) 数组从小到大排序。
先前往后做一遍 \(dp\) ：
\(f_{i , j}\) 表示 \(1\to i\) 的人只用 \(j\) 个冰淇淋收买的最大收益
然后从后往前做一遍 \(dp\) ：
\(g_{i , j}\) 表示 \(i \to n\) 的人只用 \(j\) 元钱收买的最大收益。
最后枚举 \(j\) ，表示 \(j\) 前面的人只用冰淇淋售卖，后面的人只用前收买， \(j\) 既用钱也用冰淇淋收买，用 \(ans\) 记录最大值就好了。
code按照 \(X\) 排序是因为，是冰淇淋的性价比最大
#include #define fu(x , y , z) for(int x = y ; x <= z ; x ++)#define fd(x , y , z) for(int x = y ; x >= z ; x --)using namespace std;const int N = 2005;int n , a , b , f[N][N] , g[N][N];struct node { int p , c , x;} t[N];bool cmp (node x , node y) { return x.x < y.x; }int main () { scanf ("%d%d%d" , &n , &a , &b); fu (i , 1 , n) scanf ("%d%d%d" , &t[i].p , &t[i].c , &t[i].x); sort (t + 1 , t + n + 1 , cmp); fu (i , 1 , n) { fu (j , 0 , b) { f[i][j] = f[i - 1][j]; if (j >= t[i].x * t[i].c) f[i][j] = max (f[i][j] , f[i - 1][j - t[i].x * t[i].c] + t[i].p); } } fd (i , n , 1) { fu (j , 0 , a) { g[i][j] = g[i + 1][j]; if (j >= t[i].c) g[i][j] = max (g[i][j] , g[i + 1][j - t[i].c] + t[i].p); } } int ans = 0; fu (i , 1 , n) { ans = max (ans , f[i - 1][b] + g[i][a]); ans = max (ans , f[i][b] + g[i + 1][a]); for (int j = 0 ; j <= t[i].c && b >= j * t[i].x ; j ++) { if (a < t[i].c - j) continue; ans = max (ans , f[i - 1][b - j * t[i].x] + g[i + 1][a - (t[i].c - j)] + t[i].p); } } printf ("%d" , ans); return 0;} 感觉 \(dp\) 挺重要的，要加强。
