poj1189 简单dp

简介:

http://poj.org/problem?id=1189

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
/**
poj1189 简单dp
题目大意:又是中文题~
解题思路; 总共会出现2^n种情况,我们一開始就如果有2^n个球在(1,1)点往下落。

对于每个没有挖掉的钉子(i,j):dp[i+1][j]+=dp[i][j]/2; dp[i+1][j+1]+=dp[i][j]/2; 对于挖掉的钉子(i,j):dp[i+2][j+1]+=dp[i][j]; */ #include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; bool a[2555]; int n,m; LL dp[55][55]; LL gcd(LL x,LL y) { if(y==0)return x; return gcd(y,x%y); } int main() { while(~scanf("%d%d",&n,&m)) { int k=1; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { char str[12]; scanf("%s",str); if(str[0]=='*') { a[k++]=true; } else { a[k++]=false; } //printf("%d\n",a[k-1]); } //puts(""); } memset(dp,0,sizeof(dp)); dp[1][1]=1LL<<n; for(int i=1; i<=n; i++) { int x=i*(i-1)/2; for(int j=1; j<=i; j++) { if(a[j+x]) { 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 x=1LL<<n; LL y=dp[n+1][m+1]; LL g=gcd(x,y); printf("%lld/%lld\n",y/g,x/g); } return 0; }







本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5137832.html,如需转载请自行联系原作者
相关文章
|
存储 数据采集 人工智能
中医与人工智能-基于Protégé构建知识图谱
文章目录 中医与人工智能-基于Protégé构建知识图谱 本文内容 中医数据获取 中医数据处理
中医与人工智能-基于Protégé构建知识图谱
|
4天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
15天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1313 5
|
2天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
14天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1356 87
|
2天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。
|
3天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
192 82
2025年阿里云域名备案流程(新手图文详细流程)