关键词：
?
题意：一个强盗要抢劫银行又不想被抓到，所以要进行概率分析求他在不被抓的情况下能抢最多的钱。他给定T（样例个数），N（要抢的银行的个数），P（被抓的概率要小于P）Mj（强盗能抢第j个银行Mj元钱），Pj（强盗抢第j个银行被抓的概率为Pj）。
思路：被抓的概率不好直接求出来，但可以直接求出不被抓的概率，则有状态转移方程dp[j] = max(dp[j], dp[j-b[i].money]*b[i].p)表示抢到j元钱被抓的最大的概率是多少。然后逆序遍历第一个小于P的dp的下标就是答案。
PS：数组的下标表示的是可以抢到的钱数，所以不能按100来开数组。。。。。。。。（T到吐血）
代码：
1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 #include <cstring> 7 #include <queue> 8 #include <map> 9 #include <vector> 10 #define INF 0x3f3f3f3f 11 #define FRE() freopen("in.txt","r",stdin) 12 13 using namespace std; 14 typedef long long ll; 15 const int maxn = 10000; 16 double dp[maxn]; 17 struct Bank 18 19 int money; 20 double p; 21 bb[maxn]; 22 23 int main() 24 25 ios::sync_with_stdio(false); 26 int T,n; 27 double p; 28 cin>>T; 29 while(T--) 30 31 int sum = 0; 32 cin>>p>>n; 33 for(int i = 0; i<n; i++) 34 35 cin>>bb[i].money>>bb[i].p; 36 sum += bb[i].money; 37 38 memset(dp,0,sizeof(dp)); 39 dp[0] = 1; 40 for(int i = 0; i<n; i++) 41 42 for(int j=sum; j>=bb[i].money; j--) 43 44 dp[j] = max(dp[j], dp[j-bb[i].money]*(1.0 - bb[i].p)); 45 46 47 int ans = 0; 48 for(int i = sum; i>=0; i--) 49 50 if(1-dp[i]<=p) 51 52 ans = i; 53 break; 54 55 56 cout<<ans<<endl; 57 58 return 0; 59
hdu2955robberies(01背包好题)(代码片段)
RobberiesTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):31769 AcceptedSubmission(s):11527ProblemDescriptionThe 查看详情
（背包dp）hdu-2955robberies
原题链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=2955（可能失效）题意：小偷抢劫n个银行，每个银行有两个属性，m为拥有的库存金额，p为小偷偷这个银行被抓的概率。小偷抢银行的总被抓概率不能超过V。求最多抢到的金额。分... 查看详情
2021icpc上海i.steadilygrowingsteam（dp）(代码片段)
...的ti之和相等。求出此时的最大的vi之和。题目分析一个01背包问题的变形一个01背包问题的变形一个01背包问题的变形状态表示：f[i][j][k]表示从前i张牌中& 查看详情
d-strangelunchbox(背包)(代码片段)
D-StrangeLunchbox(背包)01背包的变形，考虑令dp(i,j)dp(i,j)dp(i,j)表示容量一≥i\\gei≥i且容量二≥j\\gej≥j的最小个数。然后按照01背包转移即可。注意判无解。时间复杂度：O(nm2)O(nm^2)O(nm2)//Problem:D-StrangeLunchbox//Contest:AtCoder-SciseedPr... 查看详情
luogup2979[usaco10jan]cheesetowerss变形dp背包(代码片段)
#include<bits/stdc++.h>constintN=100+10;constintT=5000;usingnamespacestd;intn,t,k,ans;intv[N],h[N],f[T];intnow;//如果不考虑大的，x=t-h[i]//考虑大的之后，0.8*x=t-h[i]//x=(t-h[i])*1.25intmain()cin>>n>& 查看详情
codeforcegym101102acoins（01背包变形）
01背包变形，注意dp过程的时候就需要取膜，否则会出错。 代码如下：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;#defineMAXW15005#defineN155#defineLLlonglong#defineMOD1000000007intw1[N],w2[ 查看详情
hdoj2955robberies（01背包）
题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2955题意有n家银行，每家银行有两个属性：钱数m，概率p，p表示抢这家银行被逮着的概率。有一个人想抢银行，他认为只要在他抢一些银行后，被逮着的概率（指抢完所有银行被逮着的概... 查看详情
hdu2955robberies（01背包）
转载请注明出处：http://blog.csdn.net/u012860063题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955ProblemDescriptionTheaspiringRoytheRobberhasseenalotofAmericanmovies,andknowsthatthebadguysusuallygetscaughtin 查看详情
01背包-dp(代码片段)
一问题分析二代码实现packageDp_0_1_bag;importjava.io.BufferedWriter;importjava.io.FileWriter;importjava.io.IOException;publicclassbinpublicstaticvoidmain(String[]args)throwsIOExceptionintc=10;int[]w=0,2,2,6,5 查看详情
[01背包变形二维费用]837d.roundsubset(代码片段)
[01背包变形]837D.RoundSubset题目题目链接题意我们把一个数的roundness值定义为它末尾0的个数。给你一个长度为n的数列，要求你从中选出k个数，使得这些选出的数的积的roundness值最大。也就是求maxmin(∑cnt2,∑cnt5)max\\min(\\sumcn... 查看详情
01背包问题(代码片段)
01背包有n种物品，背包重量为V，接下来有每个背包的重量w[i],价值v[i],求最大的总价值。这是01背包的基本样式，首先分析问题，有两种状态，放还是不放，显然得出了我们第一个dp方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])表示前i... 查看详情
01背包问题总结(代码片段)
背包问题Title组合问题True、False问题最大最小问题题目377.组合总和Ⅳ494.目标和518.零钱兑换II139.单词拆分416.分割等和子集474.一和零322.零钱兑换公式dp[i]+=dp[i-num]dp[i]=dp[i]ordp[i-num]dp[i]=min(dp[i],dp[i-num]+1)或者dp[i]=max(dp[i],dp[i-num]+1)步骤... 查看详情
背包dp（01）(代码片段)
01背包http://acm.hdu.edu.cn/showproblem.php?pid=2546余额为体积；01背包比较明显；因为是>=5时才能消费，所以预留5的空间，计算出在余额为m-5的情况下，所能花费的最大价钱；记住，因为只要>=5，不管菜多贵，都能买；所以我们希望... 查看详情
hdu2602dp01背包(代码片段)
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2602这题是非常标准的01背包，没啥特殊的地方，很简单代码：#include<bits/stdc++.h>#defineMAXS1006usingnamespacestd;intvalue[MAXS];intmain()intT;intn,m_v,v;intf[MAXS];ci 查看详情
01背包与完全背包（dp复习）(代码片段)
01背包和完全背包都是dp入门的经典，我的dp学的十分的水，借此更新博客的机会回顾一下01背包：给定总容量为maxv的背包，有n件物品，第i件物品的的体积为w[i],价值为v[i],问如何选取才能是背包内的物品价值总和最大。stdin：5123... 查看详情
动态规划--01背包问题和完全背包问题(代码片段)
动态规划的01背包问题和完全背包问题模板01背包问题模板：//01背包问题#include<stdio.h>#include<algorithm>usingnamespacestd;constintmaxn=100;//物品的最大件数constintmaxv=1000;//V的上限intw[maxn],c[maxn],dp[maxv];intmain()//边界for(intv=0;v<=V;v++)d... 查看详情
dp01背包(代码片段)
（精选上好代码讲解产自原装进口白皮书）01背包问题有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。首先我们用朴素的方式搜索一遍：intrec(inti,intj)intres;i... 查看详情
动态规划之背包问题-01背包+完全背包+多重背包(代码片段)
01背包有n种不同的物品，每种物品分别有各自的体积v[i]，价值 w[i] 现给一个容量为V的背包，问这个背包最多可装下多少价值的物品。1for(inti=1;i<=n;i++)2for(intj=V;j>=v[i];j--)3dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//dp[V]为所求完全背包0... 查看详情