Hdu5001

小鱼儿 2021-12-10 06:41 93阅读 0赞

[Hdu5001][]

这题是我见到的第一个概率dp题.

题目大意:

给n个点和他们之间的边,n<=50,图有可能是完全图.给定一个步数s(s<=10000),一个人开始在图的点之间行走,从每一点开始走的概率相同,从每一个点走向它相邻点的每一个点的概率都是相等的.

问的是不到达一个点的概率,输出所有不到达某个点的概率.

当时是不会的,原因就是对dp的理解不深,其实概率dp也就只是求出来的概率而已,没什么特别的,说不会概率dp所以不会这个题纯属是找理由.

后来看了一下这题的题解,发现真的是,要找好递推的方向和状态的定义.

这个题状态的定义是dp\[i\]\[j\]第i步到达了j这个点的概率.然后直接暴力求

最外层是i=1-n,每一次求不到达某个点的概率.

然后内层就是对步数和到达的点的枚举.

特殊的枚举方式,对于每一个i,因为不让他到达这个点i,所以不到达点i的概率就是到达其他点的概率和,不求这个点就行了.

AC代码:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 55
    10 #define maxstep 10005
    11 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 }

posted on 2014-10-08 22:14 [Lonely patients][] 阅读( ...) 评论( ...) [编辑][Link 1] 收藏

转载于:https://www.cnblogs.com/Acmerfighting/p/4012178.html

[Hdu5001]: https://www.cnblogs.com/Acmerfighting/p/4012178.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211209/df5f0ea0754148ca8d1b54b032be3faf.png
[Lonely patients]: https://www.cnblogs.com/Acmerfighting/
[Link 1]: https://i.cnblogs.com/EditPosts.aspx?postid=4012178