`
836811384
  • 浏览: 542278 次
文章分类
社区版块
存档分类
最新评论

hdu2955 01背包变形 菜鸟见谅

 
阅读更多

在我眼中的你

年华美丽

盛开如诗


//这题的精度比较高,所以要调转一下思路。以偷到最多的钱为背包最大容量,求出不被抓的概率
//题意给的是被抓的概率P,所以不被抓的概率就是1-P
//幼稚园的老师告诉我们被抓的事件是独立的所以,f[l]=max(f[l],f[l-a[k].C]*a[k].M);
//这里是都不被抓的概率

//不过这题要注意精度

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
struct
{
 int C;
 float M;
}a[10005];
float max(float a,float b)
{
 if(a>b)return a;
 else return b;
}

int i,j,k,l,N,n,sum;
float Q;
int main()
{
 cin>>n;
 while(n--)
 {
  cin>>Q>>N;
  Q=1-Q;
  sum=0;
  for(j=0;j<N;j++)
  {
   cin>>a[j].C>>a[j].M;
   a[j].M=1-a[j].M;
   sum=sum+a[j].C;
  }
  float f[10005]={1.0};
  for(k=0;k<N;k++)
  {
   for(l=sum;l>=a[k].C;l--)
   {
    f[l]=max(f[l],f[l-a[k].C]*a[k].M);
   }
  }
  for(i=sum;i>=0;i--)
  {
   if(f[i]-Q>0.000000001)
   {
    cout<<i<<endl;
    break;
   }
  } 
 }
 return 0;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics