P8903 [USACO22DEC] Bribing Friends G 看电影

P8903 [USACO22DEC] Bribing Friends G 看电影

文章目录

• P8903 [USACO22DEC] Bribing Friends G 看电影
• • 题目描述
  • • 输入格式
    • 输出格式
    • 样例 #1
    • • 样例输入 #1
      • 样例输出 #1
    • 提示
    • • 样例 1 解释
      • 测试点性质
  • 题目大意
  • code
  • 后记

题目描述

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

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

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

输入格式

输入的第 1 行包含三个整数 $N$，$A$ 和 $B$，分别表示 Bessie 拥有的朋友的数量，哞尼的数量和冰激凌甜筒的数量。

以下 $N$ 行每行包含三个整数 P i P_i Pi​， C i C_i Ci​ 和 X i X_i Xi​，表示受欢迎度（ P i P_i Pi​），贿赂朋友 $i$ 陪 Bessie 所需要的哞尼（ C i C_i Ci​），以及从朋友 $i$ 处获得 $1$ 哞尼的折扣所需要的冰激凌甜筒的数量（ X i X_i Xi​）。

输出格式

输出陪 Bessie 的朋友们的最大受欢迎度之和，假设她以最优方案花费她的哞尼和冰激凌甜筒。

样例 #1

样例输入 #1

3 10 8
5 5 4
6 7 3
10 6 3

样例输出 #1

15

提示

样例 1 解释

Bessie 可以将 $4$ 哞尼和 $4$ 个冰激凌甜筒给奶牛 $1$，将 $6$ 哞尼和 $3$ 个冰激凌甜筒给奶牛 $3$，这样奶牛 $1$ 和 $3$ 就可以陪她，得到 $5+10=15$ 的受欢迎度。

测试点性质

• 测试点 $2-4$ 满足 $N\le 5$ 以及 C i = 1 C_i=1 Ci​=1。
• 测试点 $5-7$ 满足 $B=0$。
• 测试点 $8-10$ 满足 N , A , B , P i , C i , X i ≤ 50 N,A,B,P_i,C_i,X_i \le 50 N,A,B,Pi​,Ci​,Xi​≤50。
• 测试点 $11-15$ 满足 N , A , B , P i , C i , X i ≤ 200 N,A,B,P_i,C_i,X_i \le 200 N,A,B,Pi​,Ci​,Xi​≤200。
• 测试点 $16-20$ 没有额外限制。

感觉洛谷和oj上的翻译不太一样啊。

题目大意

现在有 $N$ 个人，每个人有一个欢迎程度 $P$ ，代价 $C$ ，代价减少 $1$ 需要冰淇淋 $X$ ，现在有 $A$ 元钱和 $B$ 个冰淇淋，求能达到的最大欢迎程度。

考试时想到了 O ( n 4 ) O(n^4) O(n4) 的朴素做法，类似背包 ，拿了60分

#include 
#define fu(x, y, z) for (int x = y; x <= z; x++)
#define LL long long
using 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 f_{i , j} fi,j​ 表示 $1\to i$ 的人只用 $j$ 个冰淇淋收买的最大收益

然后从后往前做一遍 $dp$ ：

g i , j g_{i , j} gi,j​ 表示 $i\to n$ 的人只用 $j$ 元钱收买的最大收益。

最后枚举 $j$ ，表示 $j$ 前面的人只用冰淇淋售卖，后面的人只用前收买， $j$ 既用钱也用冰淇淋收买，用 $ans$ 记录最大值就好了。

按照 $X$ 排序是因为，是冰淇淋的性价比最大

code

#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$ 挺重要的，要加强。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！