首页 > 代码库 > HDU 4050 wolf5x (概率DP 求期望)

HDU 4050 wolf5x (概率DP 求期望)



题意:有N个格子,1~N,起点在0,每个格子有一个状态(0,1,2,3),每次可以跨[a,b]步,

问走完N个格子需要步数的期望,每次尽量走小的步数,即尽量走a步,不能则走a+1,……

状态0意味着你不能踏进对应的网格。 
状态1意味着你可以??步入网格用你的左腿。 
状态2意味着你可以??步入网格用你的右腿。 
状态3意味着你可以进入网格用任何你的腿,而接下来的步骤中,您可以使用任何的腿;即你不需要遵循上述规则。


思路:借鉴了各路大神的思想理解了下。

dp[i][j] :表示走到第 i 个格子在 j 状态的期望。

当j=1时,你可以走到dp[i+k][2],dp[i+k][3],

当j=2时,你可以走到dp[i+k][1],dp[i+k][3],

当j=3时,你可以走到dp[i+k][2],dp[i+k][3],dp[i+k][1],

若i+k格子是0状态或与i状态相同则不能跨k步,即若要跨k步,则跨[a,k-1]步的格子与第i个格子状态相矛盾。



#include<stdio.h>
#include<string.h>
#include<string>
#include<map>
#include<stack>
#include<math.h>
#include<queue>
#include<vector>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 2010
#define eps 1e-5

int main()
{
	int t;
	double dp[N*2][4],p[N*2][4];
	scanf("%d",&t);
	while(t--)
	{
		int n,a,b;
		scanf("%d%d%d",&n,&a,&b);
		for(int i=1;i<=n;i++)
			scanf("%lf%lf%lf%lf",&p[i][0],&p[i][1],&p[i][2],&p[i][3]);
		for(int i=n+1;i<=n+a;i++)
			for(int j=0;j<4;j++)
				p[i][j]=(j==3);
		memset(dp,0.0,sizeof(dp));
		dp[0][3]=1;
		for(int i=0;i<=n;i++)
		{
			double p1=1.0,p2=1.0,p3=1.0;
			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][1]+p[i+j][0]);

				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][2]+p[i+j][0]);

				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];
			}
		}
		double ans=0.0;
		for(int i=1;i<=n+a;i++)
			for(int j=1;j<4;j++)
				ans+=dp[i][j];
		printf("%.6lf\n",ans);
	}
	return 0;
}