sdut2623-The number of steps（概率dp第一弹，求期望）

sdut2623–The number of steps（概率dp第一弹，求期望）

全栈程序员-用户IM • 2022年1月31日上午6:00 • 未分类

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

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 *P22+ E4 * 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账号...