Description

Solution

一开始打了一个60分的暴力DP，结果一分都没得……本地调了好久才发现是没开long long。

由于我的DP方程没有任何性质，就是一个01背包，所以就没啥可优化的了。

这个题的正解其实不是DP，而是贪心……由于是单向的走，在每个位置选用时少的机房AK总是好的，这也就等价于不在用时多的机房AK，所以开个堆存一下AK了那些机房，超时了就把时间最长的机房去掉就行了。

Code

DP:

#include <algorithm>

#include <cstdio>

#include <cstring>

typedef long long LL;

const int N = 1e5 + 10;

LL f[N];

LL n, m;

struct node {

    LL t, x;

    bool operator<(const node& a) const { return x < a.x; }

} a[N];

int main() {

    scanf("%lld%lld", &n, &m);

    for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].x, &a[i].t);

    std::sort(a+1, a+n+1);

    memset(f, 0x3f, sizeof f);

    f[0] = 0;

    LL ans = 0;

    for (int i = 1; i <= n; ++i) {

        for (int j = i; j; --j) {

            f[j] = std::min(f[j] + a[i].x - a[i-1].x, f[j-1] + a[i].x - a[i-1].x + a[i].t);

            if (f[j] <= m) ans = std::max(ans, 1ll*j);

        }

        f[0] += a[i].x - a[i-1].x;

    }

    printf("%lld\n", ans);

    return 0;

}

贪心:

#include <cstdio>

#include <algorithm>

#include <queue>

typedef long long LL;

const int N = 100000 + 10;

int n;

LL m;

struct node {

    LL x, t;

    bool operator<(const node& b) const { return t < b.t; }

} a[N];

std::priority_queue<node> q;

bool cmp(const node& a, const node& b) { return a.x < b.x; }

int main() {

    scanf("%d%lld", &n, &m);

    for (int i = 1; i <= n; ++i) {

        scanf("%lld%lld", &a[i].x, &a[i].t);

        if (a[i].x > m || a[i].t > m) { --i; --n; }

    }

    std::sort(a+1, a+n+1, cmp);

    int tmp = 0, ans = 0; LL t = 0;

    for (int i = 1; i <= n; ++i) {

        t += a[i].t;

        tmp++;

        q.push(a[i]);

        while (!q.empty() && t + a[i].x > m) {

            tmp--;

            t -= q.top().t;

            q.pop();

        }

        if (t + a[i].x <= m) ans = std::max(ans, tmp);

    }

    printf("%d\n", ans);

}

Note

开long long 开long long 开long long，这个题不开long long一分都没有，想象一下NOIp如果如此的话，我大概就gg了。
花费或价值相同的背包问题可以贪心啊！！！

巴特西

[Luogu]小Z的AK计划

Description

Solution

Code

Note

最新文章

热门文章