codeforces 167B Wizards and Huge Prize 概率dp - c++编程基础

TOP

codeforces 167B Wizards and Huge Prize 概率dp

2015-07-20 17:21:41 来源: 作者: 【大中小】浏览:3次

Tags：codeforces 167B Wizards and Huge Prize 概率

题意：给定n个对手，至少要击败其中 l 个人，现在有口袋容量为 k下面n个数字表示击败这个人的概率

下面n个数字（若为-1表示击败这个人可以获得一个金币，若>0则表示可以增加口袋容量为这个数字）

求：至少击败其中的l个人，且获得的总口袋容量 >= 获得的金币个数的概率是多少。（即任何时候金币都不能放不下）

思路：设dp[i][j][k]表示当前前i个人已经战胜j个人，且剩余口袋容量为k的概率，简单的推下公式即可。有一点需要主要，可能一开始

剩余口袋容量<0后来大于0，所以要加一个常数不让它为负，只要最后剩余容量>=0即可。详见代码：

/*********************************************************
  file name: codeforces167B.cpp
  author : kereo
  create time:  2015年02月01日 星期日 21时34分15秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=200+50; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=100000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int n,m,k; int a[N]; double p[N],dp[N][N][2*N+10]; int main(){ while(~scanf("%d%d%d",&n,&m,&k)){ memset(dp,0,sizeof(dp)); dp[0][0][N+k]=1.0; for(int i=1;i<=n;i++){ scanf("%lf",&p[i]); p[i]/=100; } for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ for(int j=0;j


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：NYOJ 323 && HDU 1532 &a..	下一篇：BZOJ 1443 JSOI2009 游戏Game 二..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: