首页 > 代码库 > zoj3329（概率dp）
zoj3329（概率dp）
题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3754
题意：有三个骰子，分别有k1,k2,k3个面。 每次掷骰子，如果三个面分别为a,b,c则分数置0，否则加上三个骰子的分数之和。 当分数大于n时结束。求游戏结束时的期望步数。
分析：这题状态转移方程挺容易想，但递推化简时又是困难重重，还是得多练习。
设dp[i]表示在i分时到达目标状态的期望，pk为投掷k分的概率，p0为回到0的概率
则dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1; 都和dp[0]有关系，而且dp[0]就是我们所求，为常数
设dp[i]=A[i]*dp[0]+B[i];
代入上述方程右边得到： dp[i]=∑(pk*A[i+k]*dp[0]+pk*B[i+k])+dp[0]*p0+1 =(∑(pk*A[i+k])+p0)dp[0]+∑(pk*B[i+k])+1;
明显 A[i]=(∑(pk*A[i+k])+p0) B[i]=∑(pk*B[i+k])+1
先递推求得A[0]和B[0]. 那么 dp[0]=B[0]/(1-A[0]);
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double A[600],B[600],p[100];int main(){ int T,n; int k1,k2,k3,a,b,c; scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c); double p0=1.0/k1/k2/k3; FILL(p,0); for(int i=1;i<=k1;i++) for(int j=1;j<=k2;j++) for(int l=1;l<=k3;l++) if(i!=a||j!=b||l!=c) p[i+j+l]+=p0; FILL(A,0);FILL(B,0); for(int i=n;i>=0;i--) { A[i]=p0;B[i]=1; for(int j=1;j<=k1+k2+k3;j++) { A[i]+=A[i+j]*p[j]; B[i]+=B[i+j]*p[j]; } } printf("%.15lf\n",B[0]/(1-A[0])); }}
zoj3329（概率dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。