題目大意：
開始位置在0,每一步可以向右向左或者不動，問走了n步後，路徑中能到達最右的期望。
解題思路：
比賽的時候，題目理解錯了，認為要回到起點。-_- -_-
由於最後到達的位置不確定，每條路徑的最右距離也不確定。
所以記dp[i][j][k]為走了i步，到達j位置，且路徑中最右位置為k時概率。
顯然k>=j 否則為0
如果k==j，這一步有兩種情況，1、剛好第一次達到最大 2、先前已經達到了最大。注意此時不能從右邊向左過來，超過了k.
如果k>j ，說明這一步沒有到達k,只能是前面的已經到達了k.
s為不動的概率，r,l分別為向右走和向左走的概率。
記開始的位置為100.
代碼：
<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
#define N 110
double dp[2][N*2][N*2]; //dp[][i][j]表示走到當前步，到達i,最右的位置為j的概率
int main()
{
int t,d,n;
double l,r,s;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%lf%lf",&d,&n,&l,&r);
s=1-l-r;
memset(dp,0,sizeof(dp));
dp[0][100][100]=1; //初始化最開始的位置
int la=0,cur;
for(int i=1;i<=n;i++)
{
cur=la^1;
for(int j=100-i;j<=100+i;j++)
{
for(int k=max(100,j);k<=200;k++) //k肯定要>=j,第一步在100無論怎麼走最右肯定大於等100
{
if(k==j) //這一步到了最右
dp[cur][j][k]=dp[la][j][k]*s+dp[la][j-1][k-1]*r+dp[la][j-1][k]*r;
else //k>j的情況 之前已經到達了最大k
dp[cur][j][k]=dp[la][j][k]*s+dp[la][j-1][k]*r+dp[la][j+1][k]*l;
}
}
la=cur;
}
double ans=0;
for(int i=(100-n);i<=100+n;i++)
for(int j=100;j<=100+n;j++)
ans=ans+dp[cur][i][j]*(j-100); //直接求期望
printf("%d %.4lf\n",d,ans);
}
return 0;
}
</SPAN>
