2016级算法第五次上机-D.AlvinZH的学霸养成记III

850 AlvinZH的学霸养成记III

思路

难题。概率DP。

第一种思考方式：直接DP

dp[i]：从已经有i个学霸到所有人变成学霸的期望。

那么答案为dp[1]，需要从后往前逆推。对于某一天，有可能会增加一个学霸or不增加。

①增加：((dp[i+1] + 1) * P)

②不增加：((dp[i] + 1) * (1-P))

其中，(P = i * (n - i) * p / (C(n,2)))，C(n,2) = (n - 1) * n / 2。其含义是：n个人中选出一非学霸一学霸的方法数/n个人中选出两人方法数。

状态转移方程：(dp[i] = (dp[i + 1] + 1) * P + (dp[i] + 1) * (1 - P))。移项化简后可得： (dp[i] = dp[i + 1] + 1 / P) 。

其实可能正着想更简单，令dp[i]表示达到班内有i个学霸的期望天数。则有dp[1] = 0。相同的分析分发，最后依然可以得到 (dp2[i] = dp[i-1] + 1/P) 。最后答案为dp[n]。

优化一下，完全不需要这个dp数组，使用一个变量累加即可得到答案。

第二种思考方式：期望叠加

每天至多有一个人转化为学霸，考虑第i个人转化为学霸的期望天数D[i]，那么所有人转化为学霸的期望天数 (ans=D[1]+D[2]+…+D[n-1])。

设第i个人转化为学霸的概率为p[i]，则第i个人转化为学霸服从几何分布。

几何分布：在n次伯努利试验中，试验k次才得到第一次成功的机率。详细地说，是：前k-1次皆失败，第k次成功的概率。

期望(EX=1*a+2*(1-a)*a+3*(1-a)^2*a+...) ，错位相减求和即可得期望为 (1/p[i])。

故 (D[i]=1/p[i]) ，而 (p[i]=p*i*(n-i)/(n*(n-1)/2))，所以 (D[i]=n*(n-1)/(2*p*i*(n-i))) ，那么我们就可以在O(n)的时间内得到ans值.

你可能已经发现，最后二者计算方法其实一模一样的，侧面证明答案正确。

分析

两种方法时间复杂度都为O(n)。

需要注意的问题是乘法溢出问题，在计算 (n*(n-1) / (2*p*i*(n-i))) 的过程中，有两个地方会溢出，一个是n(n-1)，你可以通过(double)n(n-1)防止溢出，注意(double)(n(n-1))没有效果；第二个溢出是2i(n-i)p，你可以把p放前面先计算或者把i强制转换为浮点数防止溢出。

参考资料：有关概率和期望问题的研究

参考代码一

//
// Created by AlvinZH on 2017/9/15.
// Copyright (c) AlvinZH. All rights reserved.
//

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MaxSize 100005

double dp[MaxSize];//dp[i]表示学霸数量为i时，到达目标的期望

int main()
{
    int T, n;
    double p, ans1, ans2, p1;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%lf", &n, &p);
        dp[n] = 0;

        for (int i = n-1; i > 0; i--)
        {
            ans1 = (double)i * (n-i);//选出一非学霸和一学霸
            ans2 = (double)n * (n-1) / 2;//从n个人中选两个人

            p1 = ans1 / ans2 * p;
            dp[i] = dp[i+1] + 1.0/p1;
        }
        printf("%.3lf
",dp[1]);
    }
    return 0;
}

参考代码二

//
// Created by AlvinZH on 2017/9/15.
// Copyright (c) AlvinZH. All rights reserved.
//

#include<cstdio>

int main()
{
    int T, n;
    double p, ans;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %lf", &n, &p);
        ans = 0.0;
        for(int i = 1; i < n; i++)
            ans += 1.0 * n* (n-1) / (2 * p * i * (n-i));
        printf("%.3lf
", ans);
    }
    return 0;
}