首页 > 代码库 > hdu4487（概率dp）
hdu4487（概率dp）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4487
题意：开始位置在0,每一步可以向右向左或者不动，问走了n步后，路径中能到达最右的期望。
分析：dp[i][j][k]表示走了i步，到达j位置，且路径中最右位置为k时概率。
状态转移方程：
if(j==k)dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k-1]*r+dp[last][j-1][k]*r;//原地不动，向右
else dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k]*r+dp[last][j+1][k]*l;//原地不动，向右，向左
#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-6#define N 1000010#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 dp[2][210][210];int main(){ int T,n,cas; double l,r,s; scanf("%d",&T); while(T--) { scanf("%d%d",&cas,&n); scanf("%lf%lf",&l,&r); s=1-l-r; FILL(dp,0); int last=0,cur; dp[last][100][100]=1; for(int i=1;i<=n;i++) { cur=last^1; for(int j=100-i;j<=100+i;j++) for(int k=max(j,100);k<=100+i;k++) { if(j==k)dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k-1]*r+dp[last][j-1][k]*r; else dp[cur][j][k]=dp[last][j][k]*s+dp[last][j-1][k]*r+dp[last][j+1][k]*l; } last=cur; } double ans=0; for(int i=100-n;i<=100+n;i++) for(int j=100;j<=100+n;j++) ans+=dp[cur][i][j]*(j-100); printf("%d %.4lf\n",cas,ans); }}
hdu4487（概率dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。