首页 > 代码库 > hdu 2955 Robberies
hdu 2955 Robberies
题目:
链接:点击打开链接
题意:
roy抢银行,知道每个银行的存款和被抓的概率,以及Roy能够被抓的概率,求他能够抢劫的最多的money。
思路:
dp[i]表示抢劫i块钱不被抓的概率,当i==0时,一定不会被抓,即dp[0] = 1;
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAXN 110 int m[MAXN],t,n; double p[MAXN],P; double dp[MAXN*100]; double max(double a,double b) { return a>b ? a:b; } int main() { //freopen("input.txt","r",stdin); int sum; cin>>t; while(t--) { memset(dp,0,sizeof(dp)); dp[0] = 1; sum = 0; cin>>P>>n; for(int i=0; i<n; i++) { cin>>m[i]>>p[i]; sum += m[i]; } for(int i=0; i<n; i++) { for(int j=sum; j>=m[i]; j--) { dp[j] = max(dp[j],dp[j-m[i]]*(1-p[i])); } } for(int i=sum; i>=0; i--)//注意从大到小,只要符合救输出,即为能得到的最多的money { if(dp[i]>=(1-P)) { printf("%d\n",i); break; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。