正文
sdut2623--The number of steps（概率dp第一弹，求期望）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
The number of stepsTime 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(0The
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，其它的都由它连接的点的期望求出来。![]()
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2luZGRyZWFtcw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
假设i到j的概率是pij,i到i的概率是pii,期望是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;
}
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(0The
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，其它的都由它连接的点的期望求出来。![]()
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2luZGRyZWFtcw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
假设i到j的概率是pij,i到i的概率是pii,期望是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;
}
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.
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.
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，其它的都由它连接的点的期望求出来。![]()
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2luZGRyZWFtcw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
假设i到j的概率是pij,i到i的概率是pii,期望是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;
}
3
0.3 0.7
0.1 0.3 0.6
0
3.41
提示 来源2013年山东省第四届ACM大学生程序设计竞赛概率dp的第一道题目，题目比較简单。到着求解，最后一个点到最后的期望是0，其它的都由它连接的点的期望求出来。![]()
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2luZGRyZWFtcw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
假设i到j的概率是pij,i到i的概率是pii,期望是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;
}
2013年山东省第四届ACM大学生程序设计竞赛
概率dp的第一道题目，题目比較简单。
到着求解，最后一个点到最后的期望是0，其它的都由它连接的点的期望求出来。
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2luZGRyZWFtcw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast">
假设i到j的概率是pij,i到i的概率是pii,期望是E，那么求1到4的期望是
1. E4 = 0 。
2. E3 =E3 *P33
+ E4 * P34 + 1
;
+ E4 * P34 + 1
;
3.
E2 = E2 *P22+ E4
* P24 + 1 ;
E2 = E2 *P22+ E4
* P24 + 1 ;
4.
E1 =E1 *P11 + E2
*P12 +E3 * P13 + 1
;
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;
}
