题解 | #钉子和小球#
钉子和小球
https://ac.nowcoder.com/acm/problem/16856
本题为概率dp. 同时通过重载运算符利用结构体实现分数加法与约分.
#include <iostream>
using namespace std;
char g[55][55];
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
struct node {
long long a, b;
void sim() { //约分
long long w = gcd(a, b);
a /= w, b /= w;
}
node operator / (const long long y) const { //一个分数除以一个整数
node t = *this;
t.b *= y;
t.sim();
return t;
}
node operator + (node y) const {
if (a == 0) {y.sim(); return y;}
node t = *this;
if (y.a == 0) {t.sim(); return t;}
long long p = gcd(t.b, y.b);
t.a *= (y.b / p), t.a += y.a * (t.b / p), t.b *= (y.b / p);
t.sim();
return t;
}
} f[55][55];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j ++)
cin >> g[i][j];
f[0][1].a = 1, f[0][1].b = 1;
for (int i = 1; i <= n + 1; i++)
for (int j = 1; j <= n + 1; j++)
f[i][j].b = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++) {
if (g[i][j] == '*') {
node p = f[i - 1][j];
p = p / 2;
f[i][j] = f[i][j] + p;
f[i][j + 1] = f[i][j + 1] + p;
}
else {
node p = f[i - 1][j];
f[i + 1][j + 1] = f[i + 1][j + 1] + p;
}
}
f[n][m + 1].sim();
cout << f[n][m + 1].a << '/' << f[n][m + 1].b;
return 0;
}
