2015
07-17

# 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

#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;
}