2022 Hangzhou Electric Multi school bowcraft

1006 Bowcraft

The question ：

The store offers a variety of upgrade books , Each upgrade book has $\frac{a}{A}$ The probability of being upgraded by one level , If the upgrade fails , Yes $\frac{b}{B}$ The probability of reducing the level to 0. Every book you buy , Will wait for the probability from $[0,A-1]$ Generate numbers in $a$, from $[0,B-1]$ Generate numbers in $b$. Question rises to... Under the optimal strategy $k$ The expected number of books to buy .

analysis ：

consider $dp$ solve ：$dp[i]$ From 0 Step up to $i$ The expected number of books to buy .
Suppose the current status of the book is $(a,b)$, Then we can choose to use or not ：
Make $\alpha =\frac{a}{A},\beta =\frac{b}{B}$
1. If you use this book , Then rise to $i+1$ The expectation of level is ：
$$Y=dp[i+1]=dp[i]+1+(1-\alpha )\ast (1-\beta )\ast (dp[i+1]-dp[i])+(1-\alpha )\ast \beta \ast dp[i+1])$$
Explain it. ： Our expectation of successful promotion is $dp[i]+1$, Because I want to buy a book , frequency +1; If we fail to upgrade but fail to reduce to 0 level , That is, the level remains unchanged ：$(1-\alpha )\ast (1-\beta )\ast (dp[i+1]-dp[i])$, Ahead is the probability of occurrence , Well understood. , The following is the number of such events , That is, we are from $i$ Step up to $i+1$ The number of levels ; If we fail to upgrade and the level is reduced to 0：$(1-\alpha )\ast \beta \ast dp[i+1])$, When it happens , We need to rise again to $i+1$ level , Multiply to $i+1$ Level expectations .
2. If not used ：
$$X=dp[i+1]=dp[i+1]+1$$

Explain it. ： We don't use this book to rise to $i+1$ level , But we still bought this book , frequency +1.

So we get the transfer equation ：
$$dp[i+1]=\frac{1}{AB}\sum _{a,b}min\{X,Y\}$$

Because we need to adopt the best strategy to upgrade , So if we want to use this book to upgrade , that Need to meet Expectations for use $\le$ Expectations not used $(Y\le X)$
Simplify to get $$dp[i+1]\ge dp[i]\ast \frac{\alpha -\alpha \beta +\beta }{\alpha }$$
Observe the formula , Find out $\frac{\alpha -\alpha \beta +\beta }{\alpha }$ Smaller books are easier to use , That is, the book $\frac{\alpha -\alpha \beta +\beta }{\alpha }$ The smaller the better. .
Then we will all the books $\frac{\alpha -\alpha \beta +\beta }{\alpha }$ Sort , Enumeration takes the first $t$ A small book , that
Simplification $$dp[i+1]=dp[i]+1+(1-\alpha )\ast (1-\beta )\ast (dp[i+1]-dp[i])+(1-\alpha )\ast \beta \ast dp[i+1])$$ have to :
$dp[i+1]=\frac{AB+dp[i]\ast {\sum }_{fronttSmall}\alpha +\beta -\alpha \ast \beta }{t-{\sum }_{fronttSmall}1-\alpha }$.
Then enumerate recursion , Time complexity $O(k\ast A\ast B)$

code:

struct Node {
    
    int a, b;
    double val;
    bool operator < (const Node &q) const {
    
        return val < q.val;
    } 
}q[N];
void solve() {
    
    int k, A, B;
    cin >> k >> A >> B;
    vector<double> f(k + 1, 0);
    int tot = 0;
    for(int i = 0; i < A; i++)
        for(int j = 0; j < B; j++) {
    
            tot++;
            q[tot] = {
    i, j};
            if(i) q[tot].val = 1.0 * (A * j - i * j) / (i * B);
            else q[tot].val = 1e18;
        }
    sort(q + 1, q + 1 + tot);    
    for(int i = 0; i < k; i++) {
    
        f[i + 1] = 1e20;
        double s1 = 0, s2 = 0;
        for(int j = 1; j <= tot; j++) {
    
            s1 += 1.0 * q[j].a / A + 1.0 * q[j].b / B - 1.0 * q[j].a / A * q[j].b / B;
            s2 += 1 - 1.0 * q[j].a / A;
            f[i + 1] = min(f[i + 1], 1.0 * (A * B + f[i] * s1) / (j - s2));
        }
    }
    // for(int i = 0; i <= k; i++) D(f[i]);
    printf("%.3lf\n", f[k]);

}