P6771 [USACO05MAR]Space Elevator 太空电梯

Z时代
2024-01-10
分类：技术分享

正当你dp的时候突然冒出个贪心. P6771 [USACO05MAR]Space Elevator 太空电梯

初见:多重背包,不过取物品的时候要判断一下条件.数据范围还可以,但还是TLE了,甚至还有WA.

算一下可能的最大高度,Khc<=400000.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
usingnamespace std;
int n;
struct S {
int h, a, c;
} s[410];
bool dp[4000110];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i].h >> s[i].a >> s[i].c;
dp[0] = true;
for (int i = 0; i < n; i++)
for (int k = 1; k <= s[i].c; k++)
for (int j = 4000000; j >= s[i].h; j--)        // 似乎多了个0
if (j <= s[i].a) dp[j] |= dp[j - s[i].h];
for (int j = 4000000; j >= 0; j--)
if (dp[j]) {
cout << j << endl;
break;
}
return0;
}

明明知道会爆还是试了一下

注意到:

for (int j = 4000000; j >= s[i].h; j--)
if (j <= s[i].a) dp[j] |= dp[j - s[i].h];

这里让人觉得再熟悉不过了,正确的处理方法是:

for (int j = s[i].a; j >= s[i].h; j--)
dp[j] |= dp[j - s[i].h];

这样就解决了TLE.还有WA呢.

我还真没想出来有什么问题,只是隐约地觉得这题多出来的限制条件有鬼.

然后看题解,问题出在:

比如说，现在有一块高度为
按照我们的动态转移方程，先看第一块石头，得

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
usingnamespace std;
int n;
struct S {
int h, a, c;
} s[410];
bool dp[4000110];
bool cmp(struct S x, struct S y) {
return x.a < y.a;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i].h >> s[i].a >> s[i].c;
sort(s, s + n, cmp);
dp[0] = true;
for (int i = 0; i < n; i++)
for (int k = 1; k <= s[i].c; k++)
for (int j = s[i].a; j >= s[i].h; j--)
dp[j] |= dp[j - s[i].h];
for (int j = 4000000; j >= 0; j--)
if (dp[j]) {
cout << j << endl;
break;
}
return0;
}