lightoj 1079 概率计算+01背包

小灰灰 2022-07-28 04:09 159阅读 0赞

1079 - Just another Robbery

<table> 
 <tbody> 
  <tr> 
   <td title="normal judge"><a href="http://lightoj.com/volume_submit.php?problem=1079" rel="nofollow"><img src="http://lightoj.com/images/submit1.png" alt=""> </a>&nbsp; <a href="http://udebug.com/LOJ/1079" rel="nofollow"><img src="http://lightoj.com/images/udebug.png" alt=""> </a></td> 
   <td><a href="http://lightoj.com/volume_showproblem.php?problem=1079&amp;language=english&amp;type=pdf" rel="nofollow">PDF (English) </a></td> 
   <td><a href="http://lightoj.com/volume_problemstat.php?problem=1079" rel="nofollow">Statistics </a></td> 
   <td><a href="http://lightoj.com/forum_showproblem.php?problem=1079" rel="nofollow">Forum </a></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td>Time Limit: <span style="color:#B45F04">4 second(s)</span></td> 
   <td>Memory Limit: <span style="color:#B45F04">32 MB</span></td> 
  </tr> 
 </tbody> 
</table>

As Harry Potter series is over, Harry has no job. Since hewants to make quick money, (he wants everything quick!) so he decided to robbanks. He wants to make a calculated risk, and grab as much money as possible. Buthis friends - Hermione and Ron have decided upon a tolerable probability **P**of getting caught. They feel that he is safe enough if the banks he robstogether give a probability less than **P**.

# Input #

Input starts with an integer **T (≤ 100)**,denoting the number of test cases.

Each case contains a real number **P**, the probability Harryneeds to be below, and an integer **N (0 < N ≤ 100)**, the numberof banks he has plans for. Then follow **N** lines, where line **j**gives an integer **Mj (0 < Mj ≤ 100)** and areal number **Pj** . Bank **j** contains **Mj**millions, and the probability of getting caught from robbing it is **Pj**.A bank goes bankrupt if it is robbed, and you may assume that all probabilitiesare independent as the police have very low funds.

# Output #

For each case, print the case number and the maximum numberof millions he can expect to get while the probability of getting caught isless than **P**.

<table> 
 <tbody> 
  <tr> 
   <td> <h1>Sample Input</h1> </td> 
   <td> <h1>Output for Sample Input</h1> </td> 
  </tr> 
  <tr> 
   <td> <p>3</p> <p>0.04 3</p> <p>1 0.02</p> <p>2 0.03</p> <p>3 0.05</p> <p>0.06 3</p> <p>2 0.03</p> <p>2 0.03</p> <p>3 0.05</p> <p>0.10 3</p> <p>1 0.03</p> <p>2 0.02</p> <p>3 0.05</p> </td> 
   <td> <p>Case 1: 2</p> <p>Case 2: 4</p> <p>Case 3: 6</p> </td> 
  </tr> 
 </tbody> 
</table>

# Note #

For the first case, if he wants to rob bank 1 and 2, thenthe probability of getting caught is **0.02 + (1 - 0.02) \* .03 = 0.0494**which is greater than the given probability **(0.04)**. That's why he hasonly option, just to rob rank 2.

题意: Potter要去抢银行, 每个银行有能抢的金钱数量和被警察抓到的概率, 求在总概率不超过P的情况下能抢到的最大的金钱数.每个银行只能抢一次

分析: dp\[i\]表示抢i的钱被抓的概率最小是多少, 然后逆着来,保证每个银行值抢一次, 更新最小值.

注意这里被抓的概率不是简单的相加, 而是先计算各自出不被抓的概率, 然后相乘, 最后1.0在减去不被抓的概率就是被抓的概率了,

这点应该很容易理解.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=10010,MOD=1e9+7;
    
    double dp[N],p[123];
    int val[132];
    int main()
    {
        int T=in(),ca=1;
        while(T--)
        {
            double P;
            scanf("%lf",&P);
            int n=in(),sum=0;
            for(int i=0;i<n;i++)
            {
                scanf("%d%lf",&val[i],&p[i]);
                sum += val[i];
            }
            for(int i=0;i<=sum;i++) dp[i]=inf;
            dp[0]=0;
            for(int i=0;i<n;i++)
            {
                double no=1.0-p[i];
                for(int j=sum;j>=val[i];j--)
                {
                    if(dp[j-val[i]]!=inf)
                    {
                        double tmp = no * (1.0-dp[j-val[i]]);
                        dp[j] = min(1.0-tmp,dp[j]);
                    }
                }
            }
            int ans=0;
            for(int i=sum;i;i--)
            {
                if(dp[i]<=P)
                {
                    ans=i;
                    break;
                }
            }
            printf("Case %d: %d\n",ca++,ans);
        }
        return 0;
    }