题目:
链接:点击打开链接
题意:
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; }
hdu 2955 Robberies,布布扣,bubuko.com
原文:http://blog.csdn.net/u013147615/article/details/25917369