UVALive 6672 Bonus Cards 概率dp

题意呢就是有两种售票方式一种是icpc 一种是其他方式 icpc抢票成功的概率是其他方式的2倍……

这时一个人出现了他通过内幕知道了两种抢票方式各有多少人他想知道自己如果用icpc抢票成功的概率是多少用acm抢票成功的概率是多少……

做过不多的概率dp 还在摸索……

dp[i][j]代表第i轮有j个icpc的人已经有票了……

当然同时i-j个通过其他方式抢票的人也有票了这就是用同样的函数搜两次的原理……

优化一次i<=a 一次是把初始化放到for里……

第一次见这么卡时间的题……

把dp数组的优化放到for里就过了……

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 #include<string>

 #include<map>

 #include<vector>

 #include<queue>

 #define M(a,b) memset(a,b,sizeof(a))

 using namespace std;

 double dp[][]; //i轮j个有票

 bool ok=false;

 double solve(int a,int b,int c){

     double n=(double)a;

     double icpc=(double)b;

     double acm=(double)c;

     if(n>icpc+acm) n=icpc+acm;

     if(a>b+c) a=b+c;

     dp[][]=;

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

         dp[i][]=; //优化初始化就过了

         dp[i][]+=dp[i-][]*(acm-i+1.0)/(acm-i+1.0+icpc*2.0);

     }

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

         dp[i][i]=;

         dp[i][i]+=dp[i-][i-]*((icpc-i+1.0)*2.0)/(acm+(icpc-i+1.0)*2.0);

     }

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

         for(int j=;j<i&&j<=a;j++){

             dp[i][j]=;

             //这里还可以优化

             dp[i][j]+=dp[i-][j]*(acm-(i-j-1.0))/(acm-(i-j-1.0)+(icpc-j)*2.0);

             dp[i][j]+=dp[i-][j-]*((icpc-j+1.0)*2.0)/(acm-(i-j)+(icpc-j+1.0)*2.0);

         }

     }

     double ans=;

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

         if(ok)ans+=(dp[a][i])*i/icpc;

         else ans+=(dp[a][i])*(n-i)/acm;

     return ans;

 }

 int main(){

     int n,icpc,acm;

     while(~scanf("%d",&n)){

         if(n==) break; //这里不加应该也可以

         scanf("%d%d",&icpc,&acm);

         if(icpc==&&acm==){

             printf("1.0000000000000000\n");

             printf("1.0000000000000000\n");

             continue;

         }

         ok=true;

         printf("%.16lf\n",solve(n,icpc+,acm));

         ok=false;

         printf("%.16lf\n",solve(n,icpc,acm+));

     }

     return ;

 }

巴特西

UVALive 6672 Bonus Cards 概率dp

最新文章

热门文章