爱奇艺-笔试刷题2018-07-15

题目描述：

/**
牛牛和羊羊非常无聊.他们有n + m个共同朋友,他们中有n个是无聊的,m个是不无聊的。
每个小时牛牛和羊羊随机选择两个不同的朋友A和B.
(如果存在多种可能的pair(A, B),任意一个被选到的概率相同。),
然后牛牛会和朋友A进行交谈,羊羊会和朋友B进行交谈。
在交谈之后,如果被选择的朋友之前不是无聊会变得无聊。
现在你需要计算让所有朋友变得无聊所需要的时间的期望值。
输入描述:
输入包括两个整数n 和 m(1 ≤ n, m ≤ 50)
输出描述:
输出一个实数,表示需要时间的期望值,四舍五入保留一位小数。
输入例子1:
2 1
输出例子1:
1.5
*/ 

思路如下：

概率题（采用记忆化搜索策略 O(mn)）
F(n,m)表示n个无聊，m个有聊变为全部无聊期望时间
状态(n, m)的下一个状态可能是 (n, m) (n+1, m-1) (n+2, m-2)分别对应概率为p1, p2, p3
F(n, m)=p1(F(n, m)+1)+p2(F(n+1, m-1)+1)+p3(F(n+2, m-2)+1)
total=m+n
p1=(n C 2)/(total C 2)
p2=(n C 1)*(m C 1)/(total C 2)
p3=(m C 2)/(total C 2)
p1+p2+p3=1

简化公式
(1-p1)F(n, m)=1+p2F(n+1, m-1)+p3*F(n+2, m-2)

由于此种情况n>=1 m>=1 p1肯定不为0
p1=n(n-1)/((n+m)(n+m-1))
p2=2mn/((n+m)(n+m-1))
p3=m(m-1)/((n+m)*(n+m-1))

base case:
F(n,0)=0

F(n, 负数)=0

代码如下：

#include<stdio.h>
#include<iostream>
 
#define MAX 101
 
using namespace std;
 
//标记备忘录是否有效
bool marked[MAX][MAX];
//行为n 列为m memo只记录n>=1 m>=1的情况
double memo[MAX][MAX];
 
//n在第一次进入就确保>=1,且n只会增加
//m在第一次进入确保>=1,m会减少
double DFS(int n, int m){
    if(m<=0)
        return 0;
    if(marked[n][m]){
        return memo[n][m];
    }
    double p1, p2, p3;
    p1=1.0*n*(n-1)/((n+m)*(n+m-1));
    p2=1.0*2*m*n/((n+m)*(n+m-1));
    p3=1.0*m*(m-1)/((n+m)*(n+m-1));
    memo[n][m]=1.0*(1+p2*DFS(n+1, m-1)+p3*DFS(n+2, m-2))/(1-p1);
    marked[n][m]=true;
    return memo[n][m];
}
 
int RoundDouble(double number)
{
    return (number > 0.0) ? (number + 0.5) : (number - 0.5);
}
 
int main()
{
//    double a=3.64;
//    int aInt=RoundDouble(a*10);
//    a=aInt/10.0;
//    printf("%.1lf\n", a);
    int n, m;
    scanf("%d%d", &n, &m);
    if(n<=0 || m<=0)
        return -1;
    double res=DFS(n, m);
    int resInt=RoundDouble(res*10);
    res=resInt/10.0;
    printf("%.1lf", res);
    return 0;
}