4.5算法之动态规划 191:钉子和小球 概率

题目

http://noi.openjudge.cn/ch0405/191/
描述
有一个三角形木板,竖直立放,上面钉着n(n+1)/2颗钉子,还有(n+1)个格子(当n=5时如图1)。每颗钉子和周围的钉子的距离都等于d,每个格子的宽度也都等于d,且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落,小球每碰到一个钉子都可能落向左边或右边(概率各1/2),且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi=,其中i为格子的编号,从左至右依次为0,1,…,n。
现在的问题是计算拔掉某些钉子后,小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。

输入
第1行为整数n(2 <= n <= 50)和m(0 <= m <= n)。以下n行依次为木板上从上至下n行钉子的信息,每行中’*’表示钉子还在,’.’表示钉子被拔去,注意在这n行中空格符可能出现在任何位置。
输出
仅一行,是一个既约分数(0写成0/1),为小球落在编号为m的格子中的概pm。既约分数的定义:A/B是既约分数,当且仅当A、B为正整数且A和B没有大于1的公因子。

思路

n = 2 时,第 0 层为钉子的上一层,初始小球 2^n
从第 0 层开始,第一个钉子编号为 1,第一个坑位编号为 0,对于每一个坑位考虑
– 其上方钉子空则上两层对应小球数量直接累加
– 左侧钉子不空则左侧钉子上方小球数量一半累加到该位置
– 右侧同理

最后辗转相除法求最大公约数,约分

源码

//
//  191.cpp
//  test
//
//  Created by bytedance on 2020/7/30.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
vector<vector<long long>> dp;
vector<vector<char>> cnt;
long long gcd(long long x,long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    long long n,m;
    cin >> n >> m;
    cnt.resize(n+1,vector<char>(n+1));
    dp.resize(n+1,vector<long long>(n+1,0));
    for(long long i = 1;i <= n; ++i){
        for(long long j = 1;j <= i; ++j){
            char c;
            cin >> c;
            cnt[i][j]=c;
        }
    }
    //
    dp[0][0] = pow(2,n);
    for(long long i = 1;i <= n;++i){
        for(long long j = 0;j <= i; ++j){
            //处理左右边界
            if(j == 0){
                if(cnt[i][j+1]=='*'){
                    dp[i][j]=dp[i-1][j]/2;
                }else{
                    dp[i][j]=0;
                }
            }else if(j == i){
                if(cnt[i][j]=='*'){
                    dp[i][j]=dp[i-1][j-1]/2;
                }else{
                    dp[i][j]=0;
                }
            }else{
                if(cnt[i-1][j]=='.'){
                    dp[i][j]+=dp[i-2][j-1];
                }
                if(cnt[i][j]=='*'){
                    dp[i][j]+=dp[i-1][j-1]/2;
                }
                if(cnt[i][j+1]=='*'){
                    dp[i][j]+=dp[i-1][j]/2;
                }
            }
        }
    }

    long long a = dp[n][m],b = dp[0][0];
    long long gc=gcd(b,a);
    a/=gc;
    b/=gc;
    cout << a<<"/"<<b;

    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注