Looter of Fridges Gym - 102020L （背包）

https://vjudge.net/problem/Gym-102020L

背包，按时间排序，从后往前放

struct box {
int val, w, time;
bool operator < (const box& a) {
return time > a.time;
}
}b[maxn];

struct query {
int time, limit, id, ans;
bool operator < (const query& a) {
return time > a.time;
}
}a[maxn];

bool cmp(const query& a, const query& b) {
return a.id < b.id;
}

int dp[maxn];
signed main() {
int n, q;
scanf("%lld %lld", &n, &q);
int bcnt = 0;
set st;
for (int i = 0; i < n; ++i) {
scanf("%lld %lld %lld", &b[bcnt].val, &b[bcnt].w, &b[bcnt].time);
if (b[bcnt].w <= 10000) bcnt++;
}
sort(b, b + bcnt);
int maxlimit = -1;
for (int i = 0; i < q; ++i) {
scanf("%lld %lld", &a[i].time, &a[i].limit);
a[i].id = i; maxlimit = max(maxlimit, a[i].limit);
}
sort(a, a + q);
int cnt = 0;
for (int i = 0; i < bcnt; ++i) {
while (a[cnt].time >= b[i].time) {
/if (a[cnt].time == b[i].time) {
if (cnt == 0) a[cnt].ans = 0;
else a[cnt].ans = a[cnt - 1].ans;
}
else/ a[cnt].ans = dp[a[cnt].limit];
cnt++;
}
for (int j = maxlimit; j >= b[i].w; --j) {
dp[j] = max(dp[j], dp[j - b[i].w] + b[i].val);
}
}
while (cnt < q) {
a[cnt].ans = dp[a[cnt].limit];
cnt++;
}
sort(a, a + q, cmp);
for (int i = 0; i < q; ++i) printf("%lld\n", a[i].ans);
return 0;
}

Looter of Fridges Gym - 102020L （背包）

原文：https://www.cnblogs.com/wanshe-li/p/14492642.html