「解题报告」CF739E Gosha is hunting

来南京第二天就感冒了，然后嗓子疼，头疼炸了。哈哈。

等等是不是春季赛前我也这个状态来着。呃呃。好像确实一模一样。

这玩意跟 DP 有个鬼关系。

下面两个概率用 \(u_i, v_i\) 表示。

首先如果只选两者之一，贡献为 \(u_i / v_i\)，如果两者都选那么贡献为 \(u_i + v_i - u_iv_i\)。

我们要最大化和，这东西看起来就很费用流。先建个模先。

考虑二分图模型，源点向两个点连流量 \(a, b\)，费用 \(0\) 的边，分别表示选 \(u_i\) 和 \(v_i\)。然后这两个点向每个点 \(i\) 连费用 \(u_i / v_i\)，流量 \(1\) 的边。考虑 \(-u_i v_i\) 的贡献，我们可以先从 \(i\) 向汇点连 \(0\) 费用的边，然后再连一条 \(-u_i v_i\) 费用的边，这样正好满足贡献。

然后发现一边只有两个点，这东西太模拟费用流了，直接大力模拟。大致分 \(S \to a \to i \to T\)，\(S \to b \to i \to T\)，\(S \to a \to i \to b \to j \to T\)，\(S \to b \to i \to b \to j \to T\) 四种，具体懒得写了，太麻烦了。

反正最后复杂度是 \(O(n \log n)\) 的。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
priority_queue<pair<double, int>> q[6];
int n, a, b;
double u[MAXN], v[MAXN];
int type[MAXN];
void update() {
    for (int i = 0; i < 6; i++) while (q[i].size()) {
        if (type[q[i].top().second] != i % 3) {
            q[i].pop();
        } else break;
    }
}
void insert(int x, int t) {
    type[x] = t;
    if (type[x] == 0) {
        q[0].push({ u[x], x });
        q[3].push({ v[x], x });
    }
    if (type[x] == 1) {
        q[1].push({ v[x] - u[x] * v[x], x });
        q[4].push({ v[x] - u[x], x });
    }
    if (type[x] == 2) {
        q[2].push({ u[x] - u[x] * v[x], x });
        q[5].push({ u[x] - v[x], x });
    }
}
int main() {
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &u[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        insert(i, 0);
    }
    double ans = 0;
    while (a || b) {
        int op;
        double val = -1e18;
        if (a) {
            // u[i]
            if (q[0].size() && q[0].top().first > val)
                val = q[0].top().first, op = 1;
            // u[i] - v[i] + v[j]
            if (q[3].size() && q[5].size() && 
                q[3].top().first + q[5].top().first > val)
                val = q[3].top().first + q[5].top().first, op = 2;
            // u[i] - v[i] + v[j] - u[j]v[j]
            if (q[1].size() && q[5].size() &&
                q[1].top().first + q[5].top().first > val)
                val = q[1].top().first + q[5].top().first, op = 3;
            // u[i] - u[i]v[i]
            if (q[2].size() && q[2].top().first > val)
                val = q[2].top().first, op = 4;
        }
        if (b) {
            // v[i]
            if (q[3].size() && q[3].top().first > val)
                val = q[3].top().first, op = 5;
            // v[i] - u[i] + u[j]
            if (q[0].size() && q[4].size() && 
                q[0].top().first + q[4].top().first > val)
                val = q[0].top().first + q[4].top().first, op = 6;
            // v[i] - u[i] + u[j] - u[j]v[j]
            if (q[2].size() && q[4].size() &&
                q[2].top().first + q[4].top().first > val)
                val = q[2].top().first + q[4].top().first, op = 7;
            // v[i] - u[i]v[i]
            if (q[1].size() && q[1].top().first > val)
                val = q[1].top().first, op = 8;
        }
        if (op == 1) a--, insert(q[0].top().second, 1);
        if (op == 2) a--, insert(q[5].top().second, 1), insert(q[3].top().second, 2);
        if (op == 3) a--, insert(q[5].top().second, 1), insert(q[1].top().second, 3);
        if (op == 4) a--, insert(q[2].top().second, 3);
        if (op == 5) b--, insert(q[3].top().second, 2);
        if (op == 6) b--, insert(q[4].top().second, 2), insert(q[0].top().second, 1);
        if (op == 7) b--, insert(q[4].top().second, 2), insert(q[2].top().second, 3);
        if (op == 8) b--, insert(q[1].top().second, 3); 
        update();
        ans += val;
    }
    printf("%.12lf\n", ans);
    return 0;
}