POJ-1189 钉子和小球(动态规划)
钉子和小球
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 7452 Accepted: 2262
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
状态转移方程,如果当前点没有钉子,那么会直接下落,如果有钉子,下落到左边和右边是概率都是一半
if(p[i][j]==0)
dp[i+2][j+1]+=dp[i][j];
else
{
dp[i+1][j]+=dp[i][j]>>1;
dp[i+1][j+1]+=dp[i][j]>>1;
}
初始的dp[0][0]=1<
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
char a[59];
int p[55][55];
long long int dp[59][59];
int n,m;
long long int ans1;
long long int ans2;
long long int gcd(long long int ans1,long long int ans2)
{
if(ans1==0)
return ans2;
return gcd(ans2%ans1,ans1);
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
ans1=0;
ans2=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
scanf("%s",a);
if(a[0]=='*')
p[i][j]=1;
else
p[i][j]=0;
}
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=0;i<n;i++)
{
dp[0][0]<<=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
if(p[i][j]==0)
dp[i+2][j+1]+=dp[i][j];
else
{
dp[i+1][j]+=dp[i][j]>>1;
dp[i+1][j+1]+=dp[i][j]>>1;
}
}
}
ans2=dp[n][m];
for(int i=0;i<n+2;i++)
ans1+=dp[n][i];
cout<<ans2/gcd(ans1,ans2)<<"/"<<ans1/gcd(ans1,ans2)<<endl;
}
return 0;
}
最新文章
- Oracle函数组的使用
- c#窗体虚线图形验证码设计
- NSFileManager 的基本使用方法
- <;img>; to image_tag
- Git--用git建立code库
- 相对布局RelativeLayout
- [jobdu]扑克牌顺子
- 子元素增加margin-top会增加给父元素的问题
- UT源码 005
- AIOps背景/所应具备技术能力分析(上)
- tensorflow中使用指定的GPU及GPU显存 CUDA_VISIBLE_DEVICES
- 2018牛客网暑假ACM多校训练赛(第三场)D Encrypted String Matching 多项式 FFT
- LeetCode(283. 移动零)
- js快速排序算法解析
- 网络IP和网络掩码以及网关的学习
- this小案例
- 3.对神经网络训练中Epoch的理解
- R语言学习笔记—朴素贝叶斯分类
- Vue 子路由 与 单页面多路由 的区别
- websphere设置jvm参数
热门文章
- pom.xml 配置maven私服
- my-small.ini、my-medium.ini、my-large.ini、my-huge.ini文件的作用
- 如何删除一个CSDN上自己上传的资源
- mysql学习笔记(三)
- C# 压缩 SharpZipLib
- 微信-苹果机无法播放声音Audio
- System.Web.Mvc.AJAX缺少程序集引用
- Android textview及其子类
- 支持AIRPLAY ,DLNA,MIRACAST的HDMI DONGLE
- MFC 刷新函数:Invaldate,UpdateWindow,InvaldateRect