首页 > 代码库 > Hdu5001
Hdu5001
这题是我见到的第一个概率dp题.
题目大意:
给n个点和他们之间的边,n<=50,图有可能是完全图.给定一个步数s(s<=10000),一个人开始在图的点之间行走,从每一点开始走的概率相同,从每一个点走向它相邻点的每一个点的概率都是相等的.
问的是不到达一个点的概率,输出所有不到达某个点的概率.
当时是不会的,原因就是对dp的理解不深,其实概率dp也就只是求出来的概率而已,没什么特别的,说不会概率dp所以不会这个题纯属是找理由.
后来看了一下这题的题解,发现真的是,要找好递推的方向和状态的定义.
这个题状态的定义是dp[i][j]第i步到达了j这个点的概率.然后直接暴力求
最外层是i=1-n,每一次求不到达某个点的概率.
然后内层就是对步数和到达的点的枚举.
特殊的枚举方式,对于每一个i,因为不让他到达这个点i,所以不到达点i的概率就是到达其他点的概率和,不求这个点就行了.
AC代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <math.h> 5 #include <stdlib.h> 6 #include <algorithm> 7 #include <vector> 8 using namespace std; 9 #define maxn 5510 #define maxstep 1000511 vector<int> v[maxn];12 double dp[maxstep][maxn];13 int main()14 {15 int T,n,m,i,j,k,q;16 //freopen("in.txt","r",stdin);17 scanf("%d",&T);18 while(T--)19 {20 //cout<<"1"<<endl;21 int step,f,t;22 scanf("%d%d%d",&n,&m,&step);23 for(i=1;i<=n;i++)24 v[i].clear();25 for(i=1;i<=m;i++)26 {27 scanf("%d%d",&f,&t);28 v[f].push_back(t);29 v[t].push_back(f);30 }31 for(i=1;i<=n;i++)32 {33 dp[0][i]=1.0/n;34 //printf("%lf",dp[0][i]);35 }36 for(i=1;i<=n;i++)37 {38 for(j=1;j<=step;j++)39 for(k=1;k<=n;k++)40 {41 if(k==i) continue;42 dp[j][k]=0;43 for(q=0;q<v[k].size();q++)44 if(v[k][q]==i) continue;45 else dp[j][k]+=dp[j-1][v[k][q]]*(1.0/v[k].size());46 //cout<<"dp["<<j<<"]["<<k<<"]="<<dp[j][k]<<endl;47 }48 double res=0;49 for(j=1;j<=n;j++)50 if(j==i) continue;51 else res+=dp[step][j];52 printf("%.10lf\n",res,i);53 }54 }55 return 0;56 }
Hdu5001
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。