The problem is like this:↵
You are on the origin of a number axis, each time, you can move forward, backward or stay with probability $P_f, P_b, P_s=1-P_f+P_s$ respectively, i.e., if you are on $x$ now, the next step you can move to $x+1$ with probability of $P_f$ and etc.↵
And the question is: after n steps, what's the mathematical expectation of the maximal number you have reached.↵
↵
Here's an example when $n = 2, P_f = 0.25, P_b = 0.25, P_s = 0.5$:↵
↵
~~~↵
maximal number: 1↵
fs: 0.25*0.5 = 0.125↵
sf: 0.5*0.25 = 0.125↵
fb: 0.25*0.25 = 0.0625 (since you have arrived at number 1, even if you go back, you will have maximal number 1)↵
~~~↵
↵
~~~↵
maximal number: 2↵
ff: 0.25*0.25 = 0.0625↵
~~~↵
↵
since you are on the origin, all other path will have maximal number equal to 0↵
↵
Thus the expectation is: 1*(0.125+0.125+0.0625)+2*0.0625=0.4375↵
↵
↵
↵
There is a dp solution on the problem, but I just can't quite figure out why, perhaps you can just think it over first before I give the answer.:↵
↵
UPD：↵
Sorry for the lack of constraint:↵
n <=12000, 1s, 256MB↵
↵
And the solution is like this:↵
↵
~~~↵
// let f, b be the probability P_f, P_b described above, then, P_s = 1 - f - b;↵
double dp[12010][12010];↵
dp[0][0] = 1.0;↵
↵
double ans = 0;↵
↵
for(int i = 0; i < n; i++) {↵
ans += f * dp[i][0];↵
for(int j = 0; j <= i; j++) {↵
dp[i][0]↵
}↵
}↵
+ 1][max(j - 1, 0)] += dp[i][j] * f;↵
dp[i + 1][j] += dp[i][j] * (1 - f - b);↵
dp[i + 1][j + 1] += dp[i][j] * b;↵
}↵
}↵
↵
cout<<ans<<endl;↵
~~~
You are on the origin of a number axis, each time, you can move forward, backward or stay with probability $P_f, P_b, P_s=1-P_f+P_s$ respectively, i.e., if you are on $x$ now, the next step you can move to $x+1$ with probability of $P_f$ and etc.↵
And the question is: after n steps, what's the mathematical expectation of the maximal number you have reached.↵
↵
Here's an example when $n = 2, P_f = 0.25, P_b = 0.25, P_s = 0.5$:↵
↵
~~~↵
maximal number: 1↵
fs: 0.25*0.5 = 0.125↵
sf: 0.5*0.25 = 0.125↵
fb: 0.25*0.25 = 0.0625 (since you have arrived at number 1, even if you go back, you will have maximal number 1)↵
~~~↵
↵
~~~↵
maximal number: 2↵
ff: 0.25*0.25 = 0.0625↵
~~~↵
↵
since you are on the origin, all other path will have maximal number equal to 0↵
↵
Thus the expectation is: 1*(0.125+0.125+0.0625)+2*0.0625=0.4375↵
↵
↵
↵
There is a dp solution on the problem, but I just can't quite figure out why
↵
UPD：↵
Sorry for the lack of constraint:↵
n <=
↵
And the solution is like this:↵
↵
~~~↵
// let f, b be the probability P_f, P_b described above, then, P_s = 1 - f - b;↵
double dp[
dp[0][0] = 1.0;↵
↵
double ans = 0;↵
↵
for(int i = 0; i < n; i++) {↵
ans += f * dp[i][0];↵
for(int j = 0; j <= i; j++) {↵
dp[i
}↵
}↵
dp[i + 1][j] += dp[i][j] * (1 - f - b);↵
dp[i + 1][j + 1] += dp[i][j] * b;↵
}↵
}↵
↵
cout<<ans<<endl;↵
~~~
