标签：WF ch dbinom Island ICPC2018 include Gem

题目传送门

Gem Island

解题思路

首先发现，尽管绿宝石会随机、不停的分裂，每分裂一次仅仅是随机抽取一个人多获得一块绿宝石而已。
因此考虑将题意抽象成\(1+a_1、1+a_2、1+a_3…\)的数组。因此每个\(a_i\)的概率是相同的，值为:

\[\dfrac{1}{\dbinom{n+d-1}{n-1}} \]

官方证明：

因为概率相同，我们的关注点就放在如何递推计算出前r个数的值。
将总值拆成两部分运算：一部分是第一块宝石的贡献，为：

\[\dbinom{n+d-1}{d}\times r \]

另一部分是剩余的贡献，为

\[\sum_{i=n-d}^{n-1}\dbinom{n}{i}\times S(n,i)(d-(n-i)) \]

S(i,j)表示在\(a_n\)中前r个数的最大值是多少。
答案就是概率×总值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

inline int read(void) {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return f * x;
}

const int maxn = 505;

int N, D, r;

double C[maxn << 1][maxn], S[maxn][maxn];

void init(void) {
    C[0][0] = 1;
    for (int i = 1; i <= N + D; ++ i) {
        C[i][0] = 1;
        for (int j = 1; j <= max(N, D); ++ j) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
}

int main() {
    N = read(); D = read(); r = read();
    init();
    for (int n = 1; n <= r; ++ n) {
        for (int d = 0; d <= D; ++ d) {
            S[n][d] = (n + d) * C[n + d - 1][d];
        }
    }
    for (int n = r + 1; n <= N; ++ n) {
        for (int d = 0; d <= D; ++ d) {
            for (int g = n - d; g <= n - 1; ++ g) {
                S[n][d] += C[n][g] * S[n - g][d - (n - g)];
            }
            S[n][d] += C[n + d - 1][d] * r;
        }
    }
    printf("%.10lf\n", S[N][D] / C[N + D - 1][D]);
    return 0;
}

标签：WF,ch,dbinom,Island,ICPC2018,include,Gem
From： https://www.cnblogs.com/adolf-stalin/p/17064516.html