随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    抢银行。抢每个银行被抓的几率为caught[],互为独立事件,在容忍上限内,抢最多的钱。    
 4 How to Do:    01背包,但需要改变一点。需要将能抢来的最多的钱最为背包容量。
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define max(a,b) a>b?a:b
11 double caught[102],DP[10001];
12 int money[102];
13 int main(){
14     //freopen("in.txt","r",stdin);
15     int t;
16     scanf("%d",&t);
17     while (t--){
18         double limit;
19         int banks;
20         scanf("%lf%d",&limit,&banks);
21         int i,j,sum=0;
22         for(i=0;i<banks;i++)
23             scanf("%d%lf",&money[i],&caught[i]),sum+=money[i];
24         memset(DP,0,sizeof(DP));
25         DP[0]=1.0;
26         for(i=0;i<banks;i++){
27             for(j=sum;j>=money[i];j--){
28                 DP[j]=max(DP[j],DP[j-money[i]]*(1-caught[i]));
29             }
30         }
31         for(i=sum;i>=0;i--){
32             if(DP[i]>=1-limit){
33                 printf("%d\n",i);
34                 break;
35             }
36         }
37     }
38     return 0;
39 }
40 
posted on 2012-03-13 15:51 Leo.W 阅读(1063) 评论(1)  编辑 收藏 引用

评论:
# re: hdu 2955(Robberies) 2012-07-26 18:58 | fz
写的很好,谢谢分享。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理