NBA Finals(0649)
Time limit(ms): 1000 Memory limit(kb): 65535 Submission: 404 Accepted: 128
Description
Consider two teams, Lakers and Celtics, playing a series of NBA Finals until one of the teams wins n games. Assume that the probability of Lakers winning a game is the same for each game and equal to p and the probability of Lakers losing a game is q = 1-p. Hence, there are no ties.Please find the probability of Lakers winning the NBA Finals if the probability of it winning a game is p.
(假设湖人和凯尔特人在打NBA总决赛，直到一支队伍赢下 n 场比赛，那只队伍就获得总冠军，假定湖人赢得一场比赛的概率是 p，即输掉比赛的概率为 1-p，每场比赛不可能以平局收场，问湖人赢得这个系列赛的概率(哈哈，这个出题人应该是个湖蜜))
Input
first line input the n-games (7<=n<=165)of NBA Finals
second line input the probability of Lakers winning a game p (0< p < 1)
(第一行：n 代表一支队伍获得冠军需要赢得的场数)
(第二行：p 代表湖人赢得一场比赛的概率)
Output
the probability of Lakers winning the NBA Finals
（湖人赢得冠军的概率）
Sample Input
7
0.4
Sample Output
0.289792（实际应为0.228844）
Hint
Source
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
double P[][],p;
int i,j,n;
while(cin>>n>>p)
{
for(i=;i<=n;i++)
{
P[i][]=;
P[][i]=;
}
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
{
P[i][j]=P[i-][j]*p+P[i][j-]*(-p);
}
}
cout<<P[n][n]<<endl;//cout<<P[n-3][n-3]<<endl
}
return ;
}
SWUST OJ数据有误，http://acm.swust.edu.cn/problem/649/，AC代码：cout<<P[n-3][n-3]<<endl，由于BUG，只能用C++写，用C提交WA。
AHU 0J:http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=294，反而用C++提交，WA。
注：这题输入 n 代表该比赛是 2*n+1 场 n 胜制，输入 7 即 15 场 7胜制。不可以用组合数去做，数据太大了。
用dp去做，P[i][j]的含义是：当A队（湖人队）还有 i 场比赛需要赢，才能夺得冠军，B队（凯尔特人队）还有 j 场比赛需要赢，才能夺得冠军时，A队（湖人队）获得冠军的概率，所以边界 P[i][0]=0 (1<=i<=n)（B队已经夺冠了），P[0][i]=1 (1<=i<=n)（A队已经夺冠了），要求的输出即是 P[n][n]（带入上述P[i][j]去理解）。
关于状态转移方程 P[i][j]=P[i-1][j]*p+P[i][j-1]*(1-p) 说明如下：
P[i-1][j]*p( P[i][j-1]*(1-p) )，这里是乘。表面上看，P[i-1][j]相比于P[i][j]多一个胜场，但不能凭感觉地依靠乘法原理，得到 P[i][j]*p=P[i-1][j] ( P[i][j]=P[i-1][j]/p )，原因是，P[i-1][j]相比于P[i][j]在计算时少考虑了这个胜场，P[i-1][j ]的值是大于 P[i][j]的，所以应用 P[i-1][j] 乘以 p，将这个胜场考虑进去。