TIOJ 2001：闖關遊戲

TIOJ 2001：闖關遊戲

題目大意：有 $N$ 個關卡，分成 $K$ 個連續的區段，想要一次一個區段去做練習，假設現在的區段為 $[l,r]$，已經練好了 $[l,i)$，這次想練關卡 $i$，那練到關卡 $i$ 的機率是 $\frac{t_i}{\sum_{j = l}^{\ i}\ t_j}$，否則會練到已經練過的關卡，想要以最好的分法使總共練習次數的期望值最小。

解法：可以先固定一個區段，看期望值要練幾次，假設現在區段的 $t$ 值為 $t_l\sim t_r$，那輪到 $t_i$ 的時候，設 $x = \frac{\sum_{j = l}^{\ i - 1}\ t_j}{\sum_{j = l}^{\ i}\ t_j}$，$y = \frac{t_i}{\sum_{j = l}^{\ i}\ t_j}$，那練一次的機率為 $y$，練兩次的機率為 $xy$，練三次的機率為 $x^2y$，依此類推，那麼期望值就會是 $y + 2xy + 3x^2y +... = y(1 + 2x + 3x^2+...) = \frac{y}{(1-x)^2}$，又 $1 - x = y$，所以最後是 $\frac{1}{y}$。

那令 $pre_i = \sum_{j = 1}^{i} t_j$，$p1_i = \sum_{j = 1}^{i} \frac{1}{t_j}$，$p2_i = \sum_{j = 1}^{i} \frac{pre_{j - 1}}{t_j}$。$\frac{1}{y}$ 可以寫成 $\frac{pre_{i - 1} - pre_{l-1} + t_i}{t_i} = 1 + \frac{pre_{i-1}}{t_i} - pre_{l-1}\times \frac{1}{t_i}$，那把 $l\sim r$ 的 $\frac{1}{y}$ 都加起來後會得到 $(r - l + 1) + (p2_r - p2_{l - 1}) - pre_{l-1}\times (p1_r - p1_{l-1})$。如果要 $dp$ 可以假設上一個區段結束的點為 $l$，現在在 $r$，那 $dp_r = dp_l + (r-l) + (p2_r-p2_l) - pre_l\times (p1_r-p1_l) \\ = max(-pre_l\times p1_r + dp_l - l - p2_l + pre_l\times p1_l) + r + p2_r = max (m_l\times x_r + k_l) + C_r$，可以使用一個斜率遞減，查詢遞增的 $O(N)$ 斜率優化 $dp$。

現在已經知道要如何 $dp$ 了，只差要如何分 $K$ 段，如果自己寫一個暴力，可以發現轉移次數遞增時，變化量會遞增(減)，那可以猜說它是一個凸(凹)函數，所以可以用 $\text{aliens}$ 優化，每次轉移時都將 $dp$ 值加上 $penalty$，看最後轉移次數 $>$ 或是 $≤ K$，最後將答案扣掉 $K\times penalty$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;

int N, K;
ll pre[SIZE];
double p1[SIZE], p2[SIZE];

tuple<double, double, int> st[SIZE];
int L, R;
pair<double, int> dp;

bool Del (tuple<double, double, int> t1, tuple<double, double, int> t2, double x) {
    auto [m1, k1, c1] = t1;
    auto [m2, k2, c2] = t2;
    double v1 = m1 * x + k1, v2 = m2 * x + k2;
    return v1 > v2 || (v1 == v2 && c1 >= c2);
}

bool Del (tuple<double, double, int> t1, tuple<double, double, int> t2, tuple<double, double, int> t) {
    auto [m1, k1, c1] = t1;
    auto [m2, k2, c2] = t2;
    auto [m, k, c] = t;
    double x1 = (k2 - k1) / (m1 - m2), x2 = (k - k1) / (m1 - m);
    return x1 > x2 || (x1 == x2 && c2 >= c);
}

bool ok (double penalty) {
    L = 1, R = 0;
    st[++R] = {0, 0, 0};
    dp = {0, 0};
    FOR (i, 1, N) {
        while (L + 1 <= R && Del (st[L], st[L + 1], p1[i])) L++;
        auto [m, k, cnt] = st[L];
        dp = {m * p1[i] + k + i + p2[i] + penalty, cnt + 1};
        tuple<double, double, int> t = {-pre[i], dp.F - i - p2[i] + pre[i] * p1[i], dp.S};
        while (L + 1 <= R && Del (st[R - 1], st[R], t)) R--;
        st[++R] = t;
    }
    return dp.S <= K;
}

void solve() {
    cin >> N >> K;
    FOR (i, 1, N) {
        int t;
        cin >> t;
        pre[i] = pre[i - 1] + t;
        p1[i] = p1[i - 1] + 1.00 / t;
        p2[i] = p2[i - 1] + 1.00 * pre[i - 1] / t;
    }
    double l = 0, r = N + p2[N];
    FOR (t, 1, 100) {
        double mid = (l + r) / 2;
        if (ok (mid)) r = mid;
        else l = mid;
    }
    ok (r);
    cout << fixed << setprecision (16) << dp.F - K * r << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！