本文共 1066 字，大约阅读时间需要 3 分钟。

hdu2955 Robberies

标签：01背包

/*    题意：在不被抓的概率范围内，获得最多的钱。    分析：题目输入是不被抓的概率上限P，和每个银行被抓的概率pi。          转化一下，取反P = 1 - P, pi = 1- pi。(多个独立事件的概率等于它们的积)          在获得足够多得钱的前提下，使得dp[sum]最大。(dp[sum]为抢到sum的钱不被抓的概率)          若dp[sum](不被抓) > P(被抓)，sum就是能够得到的最多的钱。*/#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 10005;int money[105];double dp[maxn], pro[105];int main(){    int T;    scanf("%d", &T);    while(T--)    {        double P;        int N, sum = 0;        scanf("%lf %d", &P, &N);        P = 1.0 - P;        for(int i = 0; i < N; i++)        {            scanf("%d %lf", &money[i], &pro[i]);            sum += money[i];            pro[i] = 1.0 - pro[i];        }        memset(dp, 0, sizeof(dp));  //ZeroOnePack template        dp[0] = 1.0;  ///dp[]        for(int i = 0; i < N; i++)            for(int j = sum; j >= money[i]; j--)                dp[j] = max(dp[j], dp[j - money[i]] * pro[i]);  //积        for(int i = sum; i >= 0; i--)            if(dp[i] - P > 0.00000001)  {
  printf("%d\n", i);  break;}    }    return 0;}
     
    
   

转载地址：http://kikxi.baihongyu.com/