题目描述
Description
有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=pi=
，其中i为格子的编号，从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
Input
第1行为整数n（2 <= n <= 50）和m（0 <= m <= n）。以下n行依次为木板上从上至下n行钉子的信息，每行中’*’表示钉子还在，’.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
Output
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
Sample Input
5 2
*
* .
* * *
* . * *
* * * * *
Sample Output
7/16
题目链接
http://poj.org/problem?id=1189
解题思路
使用DP来模拟打表。我们先把输入的数据处理成类似下面的数组：
1
1 0
1 1 1
1 0 1 1
1 1 1 1 1
dp[i][j]表示的是第i行第j列碰到的概率，dp[0][0]的初始值为1 << n，因为我们要保证处理到最后一行之前不能出现0。然后从第一层开始推，假如碰到1，此时的坐标如果是i和j的话，那么，dp[i + 1][j]和dp[i + 1][j + 1]触碰到的概率都要加上1/2，所以在这里加上dp[i][j] / 2；如果碰到了0，那么小球将会跳过这一行，然后触碰到(i + 2, j + 1)这个点，也就是说这个点的概率也要加上dp[i][j] / 2。
依次处理到最后一层，直接化简求一下概率就行了。
给dp[0][0]赋初值的时候不能直接1 << n，因为编译器会将这里的1认为是int型的，要转换一下类型。
AC代码
168K/0MS/C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
typedef long long ll;
using namespace std;
ll dp[55][55];
int s[55][55];
char str[5];
ll __gcd(ll a, ll b)
{
return b == 0 ? a : __gcd(b, a % b);
}
int main()
{
int m, n;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
scanf("%s", str);
s[i][j] = str[0] == '*';
}
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1ll << n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
if (s[i][j])
{
dp[i + 1][j] += dp[i][j] / 2;
dp[i + 1][j + 1] += dp[i][j] / 2;
}
else
{
dp[i + 2][j + 1] += dp[i][j];
}
}
}
ll num = dp[n][m];
ll den = 0;
for (int i = 0; i <= n; i++)
{
den += dp[n][i];
}
ll g = __gcd(num, den);
printf("%I64d/%I64d\n", num / g, den / g);
return 0;
}