一 . Robberies (hdu 2955)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2955
题意 小偷有个总的逃跑概率，每个银行有一个钱数和逃跑概率，问在总的逃跑概率下能最多获得多少钱？
思路：开始有0-1背包写，把概率扩大100倍，wa了，重改思路。把总价格当容量，被抓的概率为价值 在被抓的概率大于总概率时的容量为多少
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <math.h>
#include <vector>
using namespace std;
#define N 10100
#define ll long long
#define INF 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof(a));
vector<vector<int> >Q;
double dp[N],w[N];
int v[N];
int main()
{
int n,t,sum;
double p;
scanf("%d",&t);
while(t--)
{
scanf("%lf %d",&p,&n);
sum=0;
for(int i=1; i<=n; i++)
{
scanf("%d %lf",&v[i],&w[i]);
sum+=v[i];
}
met(dp,0);
dp[0]=1;
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=v[i]; j--)
{
dp[j]=max(dp[j],dp[j-v[i]]*(1-w[i]));
//printf("%d %d\n",j,dp[j]);
}
}
p=1-p;
for(int i=sum;i>=0;i--)
{
if(dp[i]>=p)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}