首页 > 代码库 > 【Foreign】开锁 [概率DP]

【Foreign】开锁 [概率DP]

2024-09-06 19:27:15   218人阅读

开锁

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

　　技术分享

Input

　　技术分享

Output

　　技术分享

Sample Input

　　4
　　5 1
　　2 5 4 3 1
　　5 2
　　2 5 4 3 1
　　5 3
　　2 5 4 3 1
　　5 4
　　2 5 4 3 1

Sample Output

　　0.000000000
　　0.600000000
　　0.900000000
　　1.000000000

HINT

　　技术分享

 

Main idea

　　一个宝箱内有一个可以开启别的宝箱的钥匙，可以选择k个宝箱，询问能开启所有宝箱的概率。

 

Source

　　我们一看就知道这是一道概率DP的题目。

　　我们发现，每个宝箱有一个对应的钥匙，那么显然若干个宝箱会构成一个环，只要开了一个环中的一个宝箱就可以开启这个环。

　　那么我们要求的就是：在n个数中选k次，已知每个环的大小，选中环中的一个元素即视为选中了这个环，问每个环都被至少选了一次的概率。

　　显然直接记概率不好计算，于是我们可以算出可行的方案数。

　　我们先求出每个环的大小，然后令 f[i][j] 表示前 i 个环选了 j 个元素的方案数，那么显然可以枚举这一个环中选了几个，那么显然有：

技术分享

　　然后我们最后用 f[num][k] / 总方案数 C(n,k) 即可。注意要用double来存，否则数字不够大。

Code

技术分享
 1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std;   9 10 const int ONE=310;11  12 int T,n,k;13 int a[ONE],vis[ONE],cnt;14 int ring[ONE],num;15 int record;16 double C[ONE][ONE];17 double f[ONE][ONE];18 19 int get()20 {    21         int res=1,Q=1;char c;22         while( (c=getchar())<48 || c>57 )23         if(c==‘-‘)Q=-1;24         res=c-48;25         while( (c=getchar())>=48 && c<=57 )26         res=res*10+c-48;27         return res*Q;28 }29 30 void Solve()31 {32         n=get();    k=get();33         34         for(int i=1;i<=n;i++) a[i]=get(),vis[i]=0;35         num=0;36         for(int i=1;i<=n;i++)37         {38             if(vis[i]) continue;39             int x=i;40             cnt=0;41             for(;;)42             {43                 vis[x]=1; x=a[x]; cnt++;44                 if(x==i) break;45             }46             ring[++num]=cnt;47         }48         49         memset(f,0,sizeof(f));50         f[0][0]=1; record=0;51         for(int i=1;i<=num;i++)52         {53             record+=ring[i];54             for(int j=1;j<=record;j++)55             {56                 for(int x=1;x<=ring[i] && x<=j;x++)57                 {58                     f[i][j] += f[i-1][j-x] * C[ring[i]][x];    59                 }60             }61         }62         63         cout<<(double)f[num][k]/C[n][k]<<endl;64 }65 66 int main()67 {68         C[0][0]=1;69         for(int i=1;i<=300;i++)70         {71             C[i][0]=1;72             for(int j=1;j<=300;j++)73             C[i][j]=C[i-1][j-1]+C[i-1][j];74         }75         76         T=get();77         while(T--)78             Solve();79         80 }
View Code

 

【Foreign】开锁 [概率DP]


联系
我们