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[1001][1010]; double p[101],A[610],B[610]; 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,0,sizeof(A)); memset(B,0,sizeof(B)); memset(p,0,sizeof(p)); double Tp=1.0/(k1*k2*k3); // cout<<Tp<<endl; for(int i=1 ; i<=k1 ; i++) { for(int j=1 ; j<=k2 ; j++) { for(int k=1 ; k<=k3 ; k++) { if(i==a&&j==b&&k==c) continue; int T=i+j+k; p[T]+=Tp; } } } for(int i=n ; i>=0 ; i--) { A[i]=Tp; B[i]=1; for(int j=3 ; j<=(k1+k2+k3) ; j++) { A[i]+=p[j]*A[i+j]; B[i]+=p[j]*B[i+j]; } } double ans=B[0]/(1-A[0]); printf("%.16f ",ans); } }