首页 > ACM题库 > HDU-杭电 > HDU 4487-Maximum Random Walk-动态规划-[解题报告]HOJ
2015
07-17

HDU 4487-Maximum Random Walk-动态规划-[解题报告]HOJ

Maximum Random Walk

问题描述 :

Consider the classic random walk: at each step, you have a 1/2 chance of taking a step to the left and a 1/2 chance of taking a step to the right. Your expected position after a period of time is zero; that is, the average over many such random walks is that you end up where you started. A more interesting question is what is the expected rightmost position you will attain during the walk.

输入:

The first line of input contains a single integer P, (1 <= P <= 15), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of four space-separated values. The first value is an integer K, which is the data set number. Next is an integer n, which is the number of steps to take (1 <= n <= 100). The final two are double precision floating-point values L and R
which are the probabilities of taking a step left or right respectively at each step (0 <= L <= 1, 0 <= R <= 1, 0 <= L+R <= 1). Note: the probably of not taking a step would be 1-L-R.

输出:

The first line of input contains a single integer P, (1 <= P <= 15), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input consisting of four space-separated values. The first value is an integer K, which is the data set number. Next is an integer n, which is the number of steps to take (1 <= n <= 100). The final two are double precision floating-point values L and R
which are the probabilities of taking a step left or right respectively at each step (0 <= L <= 1, 0 <= R <= 1, 0 <= L+R <= 1). Note: the probably of not taking a step would be 1-L-R.

样例输入:

3
1 1 0.5 0.5
2 4 0.5 0.5
3 10 0.5 0.4

样例输出:

1 0.5000
2 1.1875
3 1.4965

总共有n轮走法,每次可以向左向右或不动。 求到达最右端的期望

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
double l,r,m;
int n;
double dp[103][222][222];
void solve()
{
    m=1-r-l;
    dp[0][100][100]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=100-i;j<=100+i;j++)
        {
            for(int k=max(100,j);k<=100+i;k++)  //一定有k>=j>=100
            {
                if(j==k) dp[i][j][k]=dp[i-1][j][k]*m+dp[i-1][j-1][k-1]/*第一次到k点*/*r+dp[i-1][j-1][k]/*之前已经到过k点*/*r;
                else dp[i][j][k]=dp[i-1][j][k]*m+dp[i-1][j-1][k]*r+dp[i-1][j+1][k]*l;//k点是之前到的
            }
        }
    }
}
int main()
{
    int cas,id;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d %d %lf %lf",&id,&n,&l,&r);
        solve();
        double ans=0;
        for(int i=100;i<=100+n;i++)
            for(int j=100-n;j<=100+n;j++)
                ans+=dp[n][j][i]*(i-100);
        printf("%d %.4lf\n",id,ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/t1019256391/article/details/9942603