首页 > 代码库 > Hdu5001

Hdu5001

2024-07-26 02:13:40   223人阅读

这题是我见到的第一个概率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 }
View Code

 

Hdu5001


联系
我们