Luogu4823 [TJOI2013]拯救小矮人

发布于 2019-10-31  323 次阅读


Link

题意很清楚,不说了

首先可以根据样例确定一个基本的策略,肯定希望身高矮的先走,高的后走

考虑一个有点类似于背包的DP (学长Xiao-wen也就是讨论版那位想到了很厉害的O(nlogn)贪心)

f[i][j]表示到第i个小矮人时已经逃出去j个的最大高度

很好转移: f[i][j+1] = max(f[i][j+1],f[i][j]-a[i]),其中 0≤j≤ansans 为当前最多逃出去的小矮人

此外,考虑我们最开始想到的性质,可以按照身高+臂长进行排序,优化DP

详见代码

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2000 + 5;

int n, h;
int f[SIZE];

struct node {
    int ai, bi, tot;
} a[SIZE];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline int CMP(node a, node b)
{
    if (a.tot == b.tot) return a.ai < a.ai;
    return a.tot < b.tot;
}

int main()
{
    // freopen("data.in", "r", stdin);
    n = read();
    memset(f, -1, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        a[i].ai = read(), a[i].bi = read(), a[i].tot = a[i].ai + a[i].bi;
        f[0] += a[i].ai;
    }
    h = read();
    std::sort(a + 1, a + n + 1, CMP);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = ans; j >= 0; j--) {
            if (f[j] + a[i].bi >= h) f[j + 1] = std::max(f[j + 1], f[j] - a[i].ai);
        }
        if (f[ans + 1] >= 0) ans++;
    }
    printf("%d", ans);
    return 0;
}

苟利国家生死以,岂因祸福避趋之.