Luogu5308 [COCI2019] Quiz

发布于 20 天前  43 次阅读


Link

Sol

正着 DP 好像不好表示这一次选的这一段,正难则反就倒着 DP。设 f_i 表示从后往前的一轮还剩 i 个人的最多奖金。暴力转移就是枚举下一轮还有 j 人,即:

f_i = max_{j<i} (f_j + \frac{i-j}{i} )

有决策单调性,具体的,我们可以知道假如我们在将决策 k 转移给了决策 j ,其中 k

f_k + \frac{i - k}{i}

先由此证明决策是单调的,已知 f_i 要尽可能大。同时,i 增加时 \frac{1}{i} 是在不断减小,说明 f 是一个关于 i 的上凸函数。继续化简式子,

f_j - f_k > \frac{j - k}{i}

\frac{f_j - f_k}{j - k} > \frac{1}{i}

我们可以二分切这个上凸函数的斜率。也就是说,我们可以二分 \frac{1}{i} 切这个上凸壳 f_j 的一条直线的斜率,把 f_i 作为截距。然后做斜率优化即可。

Code

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

const int SIZE = 2e5 + 5;

int n, k;
int q[SIZE], cnt[SIZE];
double f[SIZE];

namespace GTR {
    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 (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

double slope(int i, int j) { 
    return (f[i] - f[j]) / (double) (i - j);
}

int judge(double mid) {
    int head = 1, tail = 1; q[head] = 0;
    for (int i = 1; i <= n; ++ i) {
        while (head < tail && slope(q[head], q[head + 1]) > 1.00 / i) ++ head;
        f[i] = f[q[head]] + (i - q[head]) * 1.00 / i - mid, cnt[i] = cnt[q[head]] + 1;
        while (head < tail && slope(q[tail - 1], q[tail]) < slope(q[tail], i)) -- tail;
        q[++ tail] = i;
    }
    return cnt[n] >= k;
}

int main() {
    n = read(), k = read();
    double l = -1, r = SIZE - 5, mid = 0;
    for (int i = 1; i <= 100; ++ i) {
        mid = (l + r) / 2.000;
        if (judge(mid)) l = mid;
        else r = mid;
    }
    judge(l);
    printf("%.9lf\n", f[n] + (double) mid * k);
    return 0;
}

生存 关心