首页 > 代码库 > HDU 4405 (概率DP)
HDU 4405 (概率DP)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4405
题目大意：飞行棋。如果格子不是飞行点，扔骰子前进。否则直接飞到目标点。每个格子是唯一的飞行起点，但不是唯一的飞行终点。问到达或越过终点的扔骰子期望数。
解题思路：
一个告诉你求期望应该逆推而不是正推的题。
如果正推的话，对于一个点i，如果是飞行终点，那么势必要枚举到达它的飞行起点，起点有多个，每个起点概率不一定相等，期望怎么求？
如果逆推（终点变成起点）的话，对于一个点i，如果是飞行起点，那么枚举飞行终点时，可以确保终点只会出现一次，（点被逆转过来了）
即dp[v]=dp[i] (v是i的终点)，即v点不用扔骰子，期望等于i点的期望，最重要的是v只会出现一次。
由于只要是飞行点或是起点（起点期望=0）就不用扔骰子，所以枚举v点时，要提前标记一下，这样推到这个点就不用扔骰子了。
如果是普通点，则枚举加上i+1~i+6这6个等概率的点的期望/6，再扔一次骰子期望+1。
最后ans=dp[0]。
#include "cstdio"#include "vector"#include "cstring"using namespace std;vector<int> air[100005];double dp[100005];bool vis[100005];int main(){ //freopen("in.txt","r",stdin); int n,m,u,v; while(scanf("%d%d",&n,&m)!=EOF&&n) { memset(dp,0,sizeof(dp)); memset(vis,false,sizeof(vis)); for(int i=0;i<=n;i++) air[i].clear(); for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); air[v].push_back(u); } for(int i=n;i>=0;i--) { if(!vis[i]&&i!=n) { for(int j=i+1;j<=i+6;j++) dp[i]+=dp[j]/6; dp[i]+=1; } for(int j=0;j<air[i].size();j++) { int to=air[i][j]; dp[to]=dp[i]; vis[to]=true; } } printf("%.4lf\n",dp[0]); }}
| 12186624 | 2014-11-14 21:25:00 | Accepted | 4405 | 15MS | 2720K | 920 B | C++ | Physcal |
HDU 4405 (概率DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。