学步园

转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by---cxlove

题目：给出1-n连续的方格，从0开始，每一个格子有4个状态，左右脚交替，向右跳，而且每一步的步长必须在给定的区间之内。当跳出n个格子或者没有格子可以跳的时候就结束了，求出游戏的期望步数

0：表示不能到达这个格子

1：表示左脚跳进这个格子

2：表示右脚跳进这个格子

3：随意哪个脚跳进这个格子，而且下一步随意用哪个脚

http://acm.hdu.edu.cn/showproblem.php?pid=4050 

题目是要求出游戏结束的期望步数。但是分析一下这个游戏，游戏结束的状态并不好表达

当前没有格子可以跳，需要考虑的是连续的后继格子

可以做一个转换，求出到达每一个格子，某个状态的概率。

通过概率得到期望，因为到达当前格子都是由上一步走了一步然后到达的，最终的结果就是概率之和

将大于n的部分状态3设为1，因为是不受限制的

这是由概率解得期望问题，正在 研究倒推的期望DP写法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<ctime>
#define maxn 200005
#define eps 1e-8
#define inf 2000000000
#define LL long long
#define zero(a) fabs(a)<eps
#define MOD 19901014
#define N 1000005
#define pi acos(-1.0)
using namespace std;
double dp[4004][4];
double p[4004][4];
int main(){
	int t,a,b,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%d",&n,&a,&b);
		for(int i=1;i<=n;i++)
			for(int j=0;j<4;j++)
				scanf("%lf",&p[i][j]);
		for(int i=n+1;i<=n+a;i++)
			for(int j=0;j<4;j++)
				p[i][j]=(j==3);
		memset(dp,0,sizeof(dp));
		dp[0][3]=1;
		for(int i=0;i<=n;i++){
			double p1=1,p2=1,p3=1;
			for(int j=a;j<=b;j++){
				dp[i+j][2]+=dp[i][1]*p1*p[i+j][2];
				dp[i+j][3]+=dp[i][1]*p1*p[i+j][3];
				p1*=(p[i+j][0]+p[i+j][1]);
				dp[i+j][1]+=dp[i][2]*p2*p[i+j][1];
				dp[i+j][3]+=dp[i][2]*p2*p[i+j][3];
				p2*=(p[i+j][0]+p[i+j][2]);
				dp[i+j][1]+=dp[i][3]*p3*p[i+j][1];
				dp[i+j][2]+=dp[i][3]*p3*p[i+j][2];
				dp[i+j][3]+=dp[i][3]*p3*p[i+j][3];
				p3*=p[i+j][0];
			//	cout<<dp[i+j][1]<<" "<<dp[i+j][2]<<" "<<dp[i+j][3]<<endl;
			}
		}
		double ans=0;
		for(int i=1;i<=n+a;i++)
			for(int j=1;j<4;j++)
				ans+=dp[i][j];
		printf("%.8f\n",ans);
	}
	return 0;
}