CF::GYM 100418K / Cards

Posted on By 二价氢

题目:CF::GYM 100418K

大叔都喜欢学妹,但是在新生报道的时候,学妹到达的顺序是随机的,每个学妹只能在见面的时候决定是否和她搭讪,而且只能选择一个学妹,你决定,总是放弃前个学妹,同时记下学妹中质量最高的那个,之后,一旦遇到一个质量比前个学妹都要高的学妹,就和她搭讪

求搭讪到的学妹质量最高的概率最大时的取值。

首先,这显然是个结论题,答案差不多就是,之后处理一下进位就是

当然,我们也可以暴力计算

假设出现在第个,前个的最大值为

则它的概率就是

枚举,求和,找和最大的即可

AC-Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
double p[maxn][maxn];
double f[maxn];
double calc(int k , int n)
{
    double ret = 0;
    for (int m = k ; m < n ; m++)
        for (int x = 0 ; k + x <= m ; x++)
            ret += p[m - 1][k + x - 1] * f[k + x - 1] * k * f[n - (k + x + 1)];
    return ret;
}
int main()
{
    p[0][0] = 1;
    for (int i = 1 ; i < maxn ; i++)
    {
        p[i][0] = 1;
        for (int j = 1 ; j < maxn ; j++)
            p[i][j] = p[i - 1][j] + p[i - 1][j - 1];
    }
    f[0] = 1;
    for (int i = 1 ; i < maxn ; i++)
    {
        f[i] = f[i - 1] * i;
    }
    int n , x;
    cin >> n;
    double ans = 0;
    for (int i = 1 ; i <= n ; i++)
    {
        double tans = calc(i , n);
        if (tans > ans)
        {
            x = i;
            ans = tans;
        }
    }
    cout << x << endl;
    return 0;
}