打算专题训练下DP，做一道帖一道吧~~现在的代码风格完全变了~~大概是懒了。所以。将就着看吧~哈哈
Description
For
a few months now, Roy has been assessing the security of various banks
and the amount of cash they hold. He wants to make a calculated risk,
and grab as much money as possible.
His mother, Ola, has decided upon a tolerable
probability of getting caught. She feels that he is safe enough if the
banks he robs together give a probability less than this.
Input
scenario, the first line of input gives a floating point number P, the
probability Roy needs to be below, and an integer N, the number of banks
he has plans for. Then follow N lines, where line j gives an integer Mj
and a floating point number Pj .
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .
Output
he can expect to get while the probability of getting caught is less
than the limit set.
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all
probabilities are independent as the police have very low funds.
Sample Input
Sample Output
题目大意就是：Roy抢劫银行，每家银行都有一定的金额和被抓到的概率，在已知Roy被抓的概率的情况下，求Roy被抓住情况下，可以抢到的最多的钱。
这个题目很坑的点，就是精度不止两位，但是样例却又是。。。。。。唉~
特殊数据就是Roy被抓到的概率接近于0的时候，Roy抢到的钱就是所有银行的金额的和~
简单01背包而已，注意精度问题~~
//Asimple
//#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <limits.h>
#include <time.h>
#define INF 0xfffffff
#define mod 1000000
#define swap(a,b,t) t = a, a = b, b = t
#define CLS(a, v) memset(a, v, sizeof(a))
#define debug(a) cout << #a << " = " << a <<endl
#define abs(x) x<0?-x:x
#define srd(a) scanf("%d", &a)
#define src(a) scanf("%c", &a)
#define srs(a) scanf("%s", a)
#define srdd(a,b) scanf("%d %d",&a, &b)
#define srddd(a,b,c) scanf("%d %d %d",&a, &b, &c)
#define prd(a) printf("%d\n", a)
#define prdd(a,b) printf("%d %d\n",a, b)
#define prs(a) printf("%s\n", a)
#define prc(a) printf("%c", a)
using namespace std;
typedef long long ll;
const int maxn = ;
int n, m, num, T, k, len, ans, sum;
double dp[];
double pp[maxn], p;
int mon[maxn];
void input() {
srd(T);
while( T -- ) {
scanf("%lf %d", &p, &n);
sum = ;
for(int i=; i<n; i++) {
scanf("%d %lf",&mon[i],&pp[i]);
sum += mon[i];
}
CLS(dp, );
dp[] = ;//金额为0时安全
if( p <= -1e- ) {//有被抓的概率
int i;
for(i=; i<n; i++) {
for(int j=sum; j>=mon[i]; j--) {
dp[j] = max(dp[j], (1.0-pp[i])*dp[j-mon[i]]);
}
}
for(i=sum; -dp[i]>=p; i--);
prd(i);
} else {//没有被抓的概率
prd(sum);
}
}
} int main(){
input();
return ;
}