ZOJ 3329 One Person Game(概率DP,求期望)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754

题目大意:

有三个骰子,分别有K1,K2,K3个面,一次投掷可以得到三个骰子点数加和的分数,但是,当骰子1等于A,骰子2=B,骰子3=C时,结果清零。问从0开始,分数超过N时投掷次数的期望。

分析:

dp[i] : 当前分数i超越n的期望次数;

dp[i]  =  sum(pk*dp[i+k]) + dp[0]*Tp + 1;

我们在仔细的推敲下 , 我们发现这样求是不行的。为什么?原因很简单,因为答案是dp[0] , 可是dp[0]却是未知的;

看到上面的递推式分为两部分:与dp[0]有关和与它无关,于是将dp[i]构造成一个关于它的式子:

dp[i]=A[i]*dp[0]+B[i]

然后带入原方程:

dp[i]=sum(A[i+k]*dp[0]*P[k]+B[i]*P[k])+dp[0]*Tp+1

=(sum(A[i+k]*P[k])+Tp)*dp[0]+sum(B[i]*P[k])+1

所以A[i]=sum(A[i+k]*P[k])+Tp

B[i]=sum(B[i]*P[k])+1

得到这个式子之后就可以用O(N*K)的递推求出A[0]和B[0]了。

在带回到构造出的方程中:dp[0]=A[0]*dp[0]+B[0],变形后就得到结果了。

所以:如果我们以后遇到每条式子都与推到最后的结果有关,那我们也可以采用上面的做法

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
#include<string.h>
using namespace std; typedef long long ll; double dp[][];
double p[],A[],B[]; int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n,a,b,c,k1,k2,k3;
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
memset(A,,sizeof(A));
memset(B,,sizeof(B));
memset(p,,sizeof(p));
double Tp=1.0/(k1*k2*k3);
// cout<<Tp<<endl;
for(int i= ; i<=k1 ; i++)
{
for(int j= ; j<=k2 ; j++)
{
for(int k= ; k<=k3 ; k++)
{
if(i==a&&j==b&&k==c) continue;
int T=i+j+k;
p[T]+=Tp;
}
}
} for(int i=n ; i>= ; i--)
{
A[i]=Tp;
B[i]=; for(int j= ; j<=(k1+k2+k3) ; j++)
{
A[i]+=p[j]*A[i+j];
B[i]+=p[j]*B[i+j];
}
}
double ans=B[]/(-A[]);
printf("%.16f\n",ans);
}
}
上一篇:NodeJS使用formidable实现文件上传


下一篇:reids-geo