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:

UPD： Sorry for the lack of constraint: n <= 2000, 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[2010][2010];
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 + 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;