sdut2623–The number of steps(概率dp第一弹,求期望)

sdut2623–The number of steps(概率dp第一弹,求期望)

大家好,又见面了,我是全栈君。

The number of steps


Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描写叙述

    Mary stands in a strange maze, the maze looks like a triangle(the first layer have one room,the second layer have two rooms,the third layer have three rooms …). Now she stands at the top point(the first layer), and the KEY of this maze is in the lowest layer’s leftmost room. Known that each room can only access to its left room and lower left and lower right rooms .If a room doesn’t have its left room, the probability of going to the lower left room and lower right room are a and b (a + b = 1 ). If a room only has it’s left room, the probability of going to the room is 1. If a room has its lower left, lower right rooms and its left room, the probability of going to each room are c, d, e (c + d + e = 1). Now , Mary wants to know how many steps she needs to reach the KEY. Dear friend, can you tell Mary the expected number of steps required to reach the KEY?


输入

There are no more than 70 test cases. 

 

In each case , first Input a positive integer n(0
The input is terminated with 0. This test case is not to be processed.

输出

Please calculate the expected number of steps required to reach the KEY room, there are 2 digits after the decimal point.

演示样例输入

3
0.3 0.7
0.1 0.3 0.6
0 

演示样例输出

3.41

提示

 

来源

2013年山东省第四届ACM大学生程序设计竞赛
概率dp的第一道题目,题目比較简单。
到着求解,最后一个点到最后的期望是0,其它的都由它连接的点的期望求出来。

sdut2623--The number of steps(概率dp第一弹,求期望)
假设i到j的概率是p
ij,
i到i的概率是p
ii
,期望是E,那么求1到4的期望是
1.   E4 = 0 。
2.   E3 =E3 *P33 E4 * P34 + 1 ;
3.   E2 = E2 *P22E4 * P24 + 1  ;
4.   E1 =E1 *P11 + E2 *P12 +E3 * P13 + 1  ;
记忆化搜索,最后推出要求的值
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
double dp[100][100] ;
double a , b , c , d , e ;
int i , j , n ;
int ff(int x,int y)
{
    if( x <= n && y >=(n+1)-x )
        return 1 ;
    return 0 ;
}
void f()
{

    return ;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        scanf("%lf %lf", &a, &b);
        scanf("%lf %lf %lf", &c, &d, &e);
        memset(dp,0,sizeof(dp));
        for(i = n ; i >= 1 ; i--)
        {
            for(j = (n+1)-i ; j <= n ; j++)
            {
                if(i == n && j == (n+1)-i) continue ;
                else if( i == n )
                    dp[i][j] = 1.0*( dp[i][j-1] ) + 1.0 ;
                else
                {
                    if( j == (n+1)-i )
                        dp[i][j] = a*dp[i+1][j-1] + b*dp[i+1][j] + 1.0 ;
                    else
                        dp[i][j] = c*dp[i+1][j-1] + d*dp[i+1][j] + e*dp[i][j-1] + 1.0 ;
                }
            }
        }
        printf("%.2lf\n", dp[1][n]);
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115755.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • windows下用pycharm安装tensorflow简易教程

    windows下用pycharm安装tensorflow简易教程2019.4.14更新下面的内容挺老了,建议批判性阅读,各种版本一直在变化,最好的教程,果然还是tensorflow和pytorch的英文原网。Windows下面办公还行,不是很适合开发,也就跑跑小代码。我现在一般在windows上使用SSH连接远程linux的服务器,直接使用远程配置的解释器环境(pycharm有相应SSH功能,配置一下就好),这样可以方便的开着音乐,边看资料边coding…

  • C语言排序(冒泡排序、选择排序、插入排序和快速排序)

    C语言排序(冒泡排序、选择排序、插入排序和快速排序)C语言排序(冒泡排序、选择排序、插入排序和快速排序)C语言排序什么是排序?1.冒泡排序基本思想主要思路:动态示例demo2.选择排序基本思想主要思路动态示例demo3.插入排序基本思想主要思路动态示例demo4.快速排序基本思想主要思路动态示例demoC语言排序什么是排序?就是将无序的变成有序的1.冒泡排序基本思想在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,

  • Python 九九乘法表[通俗易懂]

    Python 九九乘法表[通俗易懂]#python九九乘法表#创建外层循环控制高度i=0whilei<9:#先+=,从1开始计算i+=1#创建内层循环控制宽度j=0whilej

  • NTP时间服务器搭建「建议收藏」

    1.yuminstallntpntpdate安装NTP服务器2.NTP服务器配置:修改配置文件vi/etc/ntp.conf3./etc/init.d/ntpdrestart重启服务4.ntpq-p查看状态5.date查看当前时间6.客户机同步时间ntpdatepool.ntp.org(pool.ntp.org为服务机ip地址,pool.ntp.o…

  • SVN汉化包安装后无效果(已解决)「建议收藏」

    SVN汉化包安装后无效果(已解决)「建议收藏」SVN汉化包安装后无效果(已解决)上图是我下载的SVN客户端的版本。下图是汉化包版本然后我就按部就班的一步一步安装,但始终不能设置语言为中文后来才知道是版本不对,汉化包和客户端版本要一致才行。最后我重新下了一个版本的汉化包再安装(我就把汉化包下载在桌面上,然后点击安装的),问题解决。如下图:相关链接SVN客户端下载地址:https://tortoisesvn.net/downloa…

    2022年10月26日
  • 倒立摆的simulink模型搭建

    倒立摆的simulink模型搭建倒立摆的simulink模型搭建1.倒立摆基本背景:倒立摆,InvertedPendulum,是典型的多变量、高阶次,非线性、强耦合、自然不稳定系统。倒立摆系统的稳定控制是控制理论中的典型问题,在倒立摆的控制过程中能有效反映控制理论中的许多关键问题,如非线性问题、鲁棒性问题、随动问题、镇定、跟踪问题等。因此倒立摆系统作为控制理论教学与科研中典型的物理模型,常被用来检验新的控制理论和…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号