hdu 4487 概率dp Maximum Random Walk

總共有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;
}