题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955
#include#include using namespace std;/**************************************************************************************************************** 题意：懒得看，大致是 0/1 背包 思路：（百度的，懒得读题了） 1，可以将所用银行里的钱看作背包容量，每一家银行的钱看作重量， 2，不被抓到的概率看作价值， 3，则转移方程为：dp[ j ]=max( dp[ j ] , dp[ j - bag[ i ].v]*( 1- bag[ i ].p ) );****************************************************************************************************************/double dp[10010];struct node{ int v; double p;}bag[10010];int main(){ int T,n; double p; cin>>T; while(T--) { cin>>p>>n; int sum=0; for(int i = 0;i < n;i ++) { cin>>bag[i].v>>bag[i].p; sum+=bag[i].v; } memset(dp,0,sizeof(dp)); dp[0]=1; for(int i = 0;i < n;i ++) for(int j = sum;j >= bag[i].v;j --) dp[j]=max(dp[j],dp[j-bag[i].v]*(1-bag[i].p)); for(int i = sum;i >= 0;i --){ if(dp[i]>1-p){ cout< <