「NOIP 模拟赛」滑稽

题目大意：有 $n$ 个滑稽，第 $i$ 个滑稽有两个权值 $a_i$ 和 $b_i$，要从这 $n$ 个滑稽中选出不超过 $A$ 个滑稽给大人，不超过 $B$ 个滑稽给小人，最大化给大人的滑稽的 $a_i$ 和给小人的滑稽的 $b_i$ 之和。$A+B \leq n \leq 10^5$

$O(n^2)$

先考虑 $O(n^3)$ 的做法，设 $f[i][j][k]$ 表示前 $i$ 个元素中有 $j$ 个给大人 $k$ 个给小人的最大收益，然后将这个做法优化成 $O(n^2)$。

考虑一个贪心，如果将所有元素按照 $a_i$ 从大到小排序，那么在不影响小人选择的情况下，选越靠前的元素给大人越好。

于是可以在排序后的数组上进行DP，设 $f[i][j]$ 表示前 $i$ 个元素中 $j$ 个给小人，其余的元素选不超过 $A$ 个给大人的最大收益。

DP转移方程见代码。

#include <cstdio>
#include <algorithm>

const int N = 1005;
struct Node {
    int a, b;
    bool operator < (const Node &rhs) const {
        if (a == rhs.a) return b > rhs.b;
        return a > rhs.a;
    }
} c[N];
int f[N][N], ans;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    freopen("huaji.in", "r", stdin);
    freopen("huaji.out", "w", stdout);
    
    int n = read(), A = read(), B = read();
    for (int i = 1; i <= n; ++i) c[i].a = read();
    for (int i = 1; i <= n; ++i) c[i].b = read();
    std::sort(c + 1, c + n + 1);
    for (int i = 1; i <= n; ++i) { //前i件物品
        for (int j = 0; j <= i && j <= B; ++j) { //j件物品给b, 其余的选不超过A个给a
            f[i][j] = f[i-1][j];
            if (i - j && i - j <= A) f[i][j] = max(f[i][j], f[i-1][j] + c[i].a); //当前物品给a
            if (j) f[i][j] = max(f[i][j], f[i-1][j-1] + c[i].b); //当前物品给b
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}

$O(n \log n)$

#include <cstdio>
#include <algorithm>
#include <set>

struct Pair {
    int x, y;
    bool operator < (const Pair &rhs) const {
        if (x == rhs.x) return y < rhs.y;
        return x < rhs.x;
    }
} c[100005];

std::multiset<Pair> a, b;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
bool cmp(Pair a, Pair b) {
    return a.x > b.x;
}
long long max(long long x, long long y) {
    return x > y ? x : y;
}

int main() {
    freopen("huaji.in", "r", stdin);
    freopen("huaji.out", "w", stdout);

    int n = read(), A = read(), B = read();
    long long now = 0, ans = 0;
    for (int i = 1; i <= n; ++i) c[i].x = max(read(), 0);
    for (int i = 1; i <= n; ++i) c[i].y = max(read(), 0);
    std::sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= A; ++i) //保存A选择的
        a.insert((Pair){c[i].y - c[i].x, i}), now += c[i].x;
    for (int i = A + 1; i <= n; ++i) { //保存B选择的
        b.insert((Pair){c[i].y, i}), now += c[i].y;
        if (b.size() > B) now -= b.begin()->x, b.erase(b.begin());
    }
    ans = now;
    for (int i = A + 1; i <= A + B; ++i) { //开始反悔,令A选择第i个元素
        if (b.find((Pair){c[i].y, i}) == b.end()) //如果B没有选择这个元素
            now -= b.begin()->x, b.erase(b.begin()); //贪心丢掉最小的一个
        else now -= c[i].y, b.erase((Pair){c[i].y, i}); //丢掉这个元素
        now += c[i].x; //A选择这个元素
        a.insert((Pair){c[i].y - c[i].x, i});
        now += (--a.end())->x, a.erase(--a.end()); //把一个元素从A中移到B中
        ans = max(ans, now);
    }
    printf("%lld\n", ans);

    fclose(stdin);
    fclose(stdout);
    return 0;
}