hdu 5001 概率DP 图上的DP

本文主要是介绍hdu 5001 概率DP 图上的DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=5001

当时一看是图上的就跪了 不敢写，也没退出来DP方程  

感觉区域赛的题  一则有一个点难以想到 二则就是编码有点难度。

这个题：

我一直的思路就是1-能到达i的概率 就是不能到达i的概率，然后三维方程巴拉巴拉，，，，把自己搞迷糊

正确做法：
dp[k][j]   经过j步到达k点 并且不经过i点的概率 这么设的原因是，就可以求不能到达i点的概率了。   不能到达i点的概率就是segma(dp[v][j-1]/g[v].size（）)    v是与k相邻的结点，如果j-1步到达v 第j步就有1/g[v].size()的可能性到达k点 

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000;const int MAXN = 60;
const int MAX = 10000+100;double ans[MAXN];
double dp[MAXN][MAX];
vector<int>g[MAX];
int n,m,d;void solve()
{for(int i=1;i<=n;i++){CL(dp,0);for(int j=1;j<=d;j++){if(j==1){for(int k=1;k<=n;k++)if(k!=i) dp[k][j]=1.0/n;  //第一步随机选一个点，可以到达任何一个点，所以概率都是1.0/n}else{for(int k=1;k<=n;k++)if(k!=i){for(int t=0;t<g[k].size();t++){int v=g[k][t];if(v!=i)dp[k][j]+=dp[v][j-1]/g[v].size();}}}}double out=0.0;for(int j=1;j<=n;j++)if(j!=i)out+=dp[j][d];printf("%.10lf\n",out);}
}int main()
{//IN("hdu5001.txt");int ncase;scanf("%d",&ncase);while(ncase--){for(int i=0;i<=n;i++)g[i].clear();// for(int i=0;i<=n;i++)ans[i]=0.0;scanf("%d%d%d",&n,&m,&d);d++;//int u,v;for(int i=0;i<m;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}solve();}return 0;
}

这篇关于hdu 5001 概率DP 图上的DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---