3686.贪心
2026-10-21
题解
容易发现可以通过调整答案序列中物品的顺序,使其能够划分成三个连续部分:A 和 B 都买的、A 或 B 其中一个买的、A 和 B 都不买的。
观察一下 A 或 B 其中一个人买的部分,容易发现必须满足不增,否则不可能由一个人购买,那么不妨 DP:f[i][j][k] 表示公共部分花费 i,A 花费 j 元,B 花费 k 元的最大收益。
初始状态为:f[i][A−i][B−i]=0,直接根据物品转移即可。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
#define LOCAL
namespace IO {
#ifndef LOCAL
#define SIZE (1<<20)
char in[SIZE] , *p1=in , *p2=in , out[SIZE] , *p3=out;
#define getchar() (p1==p2 && (p2=(p1=in)+fread(in,1,SIZE,stdin)) , p1==p2 ? EOF : *p1 ++)
#define flush() (fwrite(out,1,p3-out,stdout) , p3=out)
#define putchar(c) (p3==out+SIZE && flush() , *p3 ++ = c)
class Flush{public: ~Flush(){flush();} } ___;
#endif
inline int read() {
int x = 0 , f = 1;
int c = getchar();
while(c < '0' || '9' < c) {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = (x<<3) + (x<<1) + c - '0';
c = getchar();
}
return x*f;
}
inline void write(LL x , bool f = true) {
if(x < 0) x = -x , putchar('-');
static short stk[80] , top; top = 0;
do {stk[++ top] = x%10 , x/=10; } while(x);
while(top) putchar(stk[top --] | '0');
if(f) putchar('\n');
else putchar(' ');
}
#ifndef LOCAL
#undef getchar
#undef SIZE
#undef flush
#undef putchar
#endif
} using namespace IO;
const int N = 160;
const LL NINF = 0xc0c0c0c0c0c0c0c0;
struct Node {
int c; LL wa , wb;
};
inline void Max(LL& a , LL b) {
if(b > a) a = b;
}
int n , A , B;
Node a[N];
LL f[N][N][N];
int main() {
n = read(); A = read(); B = read();
for(int i = 1 ; i <= n ; i ++)
a[i].c = read() , a[i].wa = read() , a[i].wb = read();
sort(a+1 , a+n+1 , [](const Node& a , const Node& b) {
return a.c > b.c;
});
for(int i = 0 ; i <= A && i <= B ; i ++) {
for(int j = 0 ; j <= A ; j ++)
for(int k = 0 ; k <= B ; k ++)
f[i][j][k] = NINF;
f[i][A-i][B-i] = 0;
}
for(int _ = 1 ; _ <= n ; _ ++) {
int c = a[_].c; LL wa = a[_].wa , wb = a[_].wb;
for(int i = 0 ; i <= A && i <= B ; i ++)
for(int j = 0 ; j <= A ; j ++)
for(int k = 0 ; k <= B ; k ++) {
if(f[i][j][k] == NINF) continue;
if(i >= c) Max(f[i-c][j][k] , f[i][j][k]+wa+wb);
if(j >= c && k < c) Max(f[i][j-c][k] , f[i][j][k]+wa);
if(k >= c && j < c) Max(f[i][j][k-c] , f[i][j][k]+wb);
}
}
LL ans = 0;
for(int j = 0 ; j <= A ; j ++)
for(int k = 0 ; k <= B ; k ++)
Max(ans , f[0][j][k]);
write(ans);
return 0;
}