卧薪尝胆,厚积薄发。
NOI1999 钉子和小球
Date: Fri Jul 27 21:32:42 CST 2018 In Category: NoCategory

Description:

正三角形的木板上钉着钉子, 钉子排成三角形,问拔掉一些钉子后让一个小球自由滚落到最底层某个位置的概率。
$1\le n \le 50$

Solution:

$DP$ ,分情况讨论,注意上方没有钉子的情况。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
#define MAXN 52
inline char getc()
{
register char c = getchar();
while(c != '*' && c != '.')c = getchar();
return c;
}
typedef unsigned long long ll;
char p[MAXN][MAXN];
ll gcd(ll a,ll b){return (b == 0ull ? a : gcd(b,a % b));}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
struct frac
{
ll a,b;
frac(){a = 0ull;b = 1ull;}
frac friend operator + (frac x,frac y)
{
frac res;
ll t = gcd(x.b,y.b);
res.a = (x.a * (y.b / t)) + (y.a * (x.b / t));
res.b = x.b / t * y.b;
return res;
}
frac friend operator / (frac x,ll k)
{
ll t = gcd(x.a,k);
x.a /= t;x.b *= k / t;
return x;
}
void set(){a = 1ull;b = 1ull;return;}
};
frac f[MAXN][MAXN];
void pt(frac k)
{
cout << k.a << "/" << k.b << endl;
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= i;++j)
{
p[i][j] = getc();
}
}
f[1][1].set();
++n;
for(int i = 2;i <= n;++i)
{
for(int j = 1;j <= i;++j)
{
if(j > 1 && p[i - 1][j - 1] == '*')f[i][j] = f[i][j] + (f[i - 1][j - 1] / 2ull);
if(j < i && p[i - 1][j] == '*')f[i][j] = f[i][j] + (f[i - 1][j] / 2ull);
if(i > 2 && j > 1 && p[i - 2][j - 1] == '.')f[i][j] = f[i][j] + f[i - 2][j - 1];
}
}
++m;
pt(f[n][m]);
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡