hdu 2955 Robberies

题目：

链接：点击打开链接

题意：

roy抢银行，知道每个银行的存款和被抓的概率，以及Roy能够被抓的概率，求他能够抢劫的最多的money。

思路：

dp[i]表示抢劫i块钱不被抓的概率，当i==0时，一定不会被抓，即dp[0] = 1;

代码：

#include
  
   
#include
   
     #include
    
      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
     
      >m[i]>>p[i]; sum += m[i]; } for(int i=0; i
      
       =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; }