P2719 搞笑世界杯

分析：

虽然很简单的一道题，但感觉自己理解起来还是有难度。
首先，确定状态为 (dp[i][j]) 表示有 (i) 张 (A)和 (j) 张 (B) 时，最后两人票相同的概率。那么，显然 (dp[i][0]=dp[0][i]=1 (igeq 2))。又有 (dp[i][j]=0.5*(dp[i-1][j]+dp[i][j-1]))，怎么理解这个呢？第一个拿票的人，有两种选择：(A) 或者 (B)，概率各为：(frac{1}{2})。剩下的就转化为 (i-1) 张 (A),(j) 张 (B) 和 (i-1) 张 (A),(j) 张 (B)的情况。

代码：

#include<bits/stdc++.h>

using namespace std;
const int N=1300;
double dp[N][N];
int main()
{
    int n;
    scanf("%d",&n);
    n/=2;
    for(int i=2;i<=n;i++)
        dp[i][0]=dp[0][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            dp[i][j]=(dp[i-1][j]+dp[i][j-1])*0.5;
    }
    printf("%.4f
",dp[n][n]);
    return 0;
}