hdu4487（概率dp）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4487

题意：开始位置在0,每一步可以向右向左或者不动，问走了n步后，路径中能到达最右的期望。

分析：dp[i][j][k]表示走了i步，到达j位置，且路径中最右位置为k时概率。

状态转移方程：

if(j==k)dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k-1]*r+dp[last][j-1][k]*r;//原地不动，向右
else dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k]*r+dp[last][j+1][k]*l;//原地不动，向右，向左

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 1000010
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
double dp[2][210][210];
int main()
{
    int T,n,cas;
    double l,r,s;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&cas,&n);
        scanf("%lf%lf",&l,&r);
        s=1-l-r;
        FILL(dp,0);
        int last=0,cur;
        dp[last][100][100]=1;
        for(int i=1;i<=n;i++)
        {
            cur=last^1;
            for(int j=100-i;j<=100+i;j++)
                for(int k=max(j,100);k<=100+i;k++)
            {
                if(j==k)dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k-1]*r+dp[last][j-1][k]*r;
                else dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k]*r+dp[last][j+1][k]*l;
            }
            last=cur;
        }
        double ans=0;
        for(int i=100-n;i<=100+n;i++)
            for(int j=100;j<=100+n;j++)
            ans+=dp[cur][i][j]*(j-100);
        printf("%d %.4lf
",cas,ans);
    }
}