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

题目大意:

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

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

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

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

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

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

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

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

AC代码:

1 #include 
         
           2 #include 
          
            3 #include 
           
             4 #include 
            
              5 #include 
             
               6 #include 
              
                7 #include 
               
                 8 using namespace std; 9 #define maxn 5510 #define maxstep 1000511 vector
                
                  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"<