P6771 [USACO05MAR]Space Elevator 太空电梯

正当你dp的时候突然冒出个贪心.

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

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

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace 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;
        }

    return 0;
}

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

注意到:

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呢.

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

然后看题解,问题出在:

比如说，现在有一块高度为 1 的石头，不能超过高度100；还有一块高度为 10 的石头，不能超过高度 10.

按照我们的动态转移方程，先看第一块石头，得f[1]=1；然后就无法再堆任何石头了.

(转载于https://www.luogu.com.cn/blog/288716/solution-p6771)

明白了,这就去排序每个石头,关键字是高度限制,限制强的放前面.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace 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;
        }

    return 0;
}

View AC Code

所以说从现在不能无脑写模板了,觉得诡异的地方一定多想一下.

虽然只是多了个排序,但你应该意识到dp有时候不如搜索那样强悍,对数据可能是会有一点要求的.