概率DP hdu 3366 .

题意：一个人被困在一个城堡里，面前有n条路，他自己有m百万元，选择每一条路都有p概率通过，q概率遇到士兵，1-p-q概率道路不通；遇到士兵的话需要上交1百万，如果不够钱，则被杀死，问的是最优情况下多少概率可以成功逃脱

思路是首先处理一下数据，想要最优肯定是在不被杀死的情况下越早走出越好，那就要求尽量不要碰到士兵，所以应该先对数据按照p/q排序一下，这样可以保证不死的概率最大，然后通过概率dp的方程即可得解

dp[i][j]代表第i条路还有j百万的情况

第i条路逃脱的情况是dp[i][j]*pi，第i条路碰到士兵并且不被杀死的情况可以推导出dp[i+1][j-1]的情况qi*dp[i][j]，第i条路不通折返的情况是dp[i][j]*(1-pi-qi)

注意：因为概率是每次+=，所以要记得将dp数组清零
————————————————
版权声明：本文为CSDN博主「WShuo97」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/kuhuaishuxia/article/details/52042586

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=+;

 struct node

 {

     double p,q;

 }a[maxn];

 double dp[maxn][maxn];

 bool cmp(node x,node y)

 {

     return x.p*y.q>x.q*y.p;

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     for(int T=; T<=t; T++){

         int n,m;

         scanf("%d%d",&n,&m);

         for(int i=; i<=n; i++){

             scanf("%lf%lf",&a[i].p,&a[i].q);

         }

         sort(a+,a++n,cmp);

         memset(dp,,sizeof(dp));

         dp[][m]=1.0;

         double ans=;

         for(int i=;i<=n;i++)

         for(int j=m;j>=;j--){

             dp[i+][j-]+=a[i].q*dp[i][j];

             dp[i+][j]+=dp[i][j]*(-a[i].p-a[i].q);

             ans+=dp[i][j]*a[i].p;

         }

         printf("Case %d: %.5lf\n",T,ans);

     }

     return ;

 }

巴特西

概率DP hdu 3366 .

最新文章

热门文章