题目梗概

世界会售卖两种票，一种是A票，一种是B票。它们的数量都是n。

假设前面的人买A,B票的概率一定是1/2的情况下。

问如果队尾的两个人，买到同一种票的概率是多少。 

思考

接触的第一道概率相关的题目，不知道算不算dp。

首先两个人买到同一种票的情况有两种，一种是AA票 一种是BB票。

所以我们关注的重点应该是 A,B票的数量。

$dp\left [ i \right ]\left [ j \right ] = \left (dp\left [ i-1 \right ] \left [ j \right ] + dp\left [ i \right ] \left [ j-1 \right ]  \right ) \times \frac{1}{2}$

从1,1到n,n 计算每次i张A票 j张B票的 概率

需要注意的是特殊处理的 $dp\left [ i \right ]\left [ 0 \right ] \left ( i\in 1  \mapsto   n  \right )$ 

$dp\left [ 0 \right ]\left [ j \right ] \left ( j \in 1  \mapsto   n  \right )$

#include <cstdio>#include <iostream>#include <algorithm>double dp[1333][1333];int n;int main(){    scanf("%d",&n);    //n = A 票 + B票     dp[1][1]=0;    for(int i=2;i<=n/2;i++)            dp[i][0]=dp[0][i]=1;    for(int i=1;i<=n/2;i++)        for(int j=1;j<=n/2;j++)            dp[i][j] = (dp[i-1][j]+dp[i][j-1])*0.5;    printf("%.4f\n",dp[n/2][n/2]);    return 0;    }

[概率dp]CodeVs1060 搞笑世界杯