wqs 二分显然，最多每轮得分是 1，lambda 上限可置为 1。
直接 dp 复杂度 O(n2) 可以拿 34 分。

const int N = int(1e5) + 9;
pair<DB, int> f[N];
int q[N], cz, op;
int n, k;

bool ok(DB lambda) {
    cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {
        auto g = [&](int j){
            return MP(f[j].fi + (DB)(i-j)/i - lambda, f[j].se + 1);
        };
        f[i] = {0, 0};
        REP(j, i) checkMax(f[i], g(j));
    }
    return f[n].se <= k;
}

DB gao() {
    DB l = 0, r = 1;
    DO(133) {
        DB m = (l + r) / 2;
        ok(m) ? r = m : l = m;
    }
    ok(l);
    return f[n].fi + l*k;
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    RD(n, k);
    printf("%.9f\n", gao());
}

进一步观察，显然可以斜率 dp，复杂度 O(n)。

const int N = int(1e5) + 9;
pair<DB, int> f[N];
int q[N], cz, op;
int n, k;

// f[j].fi - j/i
// b = y - kx
// f[i] , f[j], 1/i, j

DB det(DB x1, DB y1, DB x2, DB y2){
    return x1<em>y2 - x2</em>y1;
}

int dett(int a, int b, int c) {
    DB t = det(b-a, f[b].fi-f[a].fi, c-a, f[c].fi-f[a].fi);
    return t &lt; 0 ? -1 : t &gt; 0;
}

bool ok(DB lambda) {
    cz = 0, op = 0; q[cz] = 0; REP_1(i, n) {
        auto g = [&amp;](int j){
            return MP(f[j].fi + (DB)(i-j)/i - lambda, f[j].se + 1);
        };
        while (cz &lt; op &amp;&amp; g(q[cz]) &lt;= g(q[cz+1])) ++cz;
        f[i] = g(q[cz]);
        while (cz &lt; op &amp;&amp; dett(q[op-1], q[op], i) &gt; 0) --op;
        q[++op] = i;
    }
    return f[n].se &lt;= k;
}

DB gao() {
    DB l = 0, r = 1;
    DO(133) {
        DB m = (l + r) / 2;
        ok(m) ? r = m : l = m;
    }

<pre><code>ok(l);
return f[n].fi + l*k;
</code></pre>

}

int main() {

#ifndef ONLINE_JUDGE
    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);
    //freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif
    RD(n, k);
    printf(&quot;%.9f\n&quot;, gao());
}

似乎也可以直接二分导数？

Posted by xiaodao
Category: 日常