https://vjudge.net/problem/HDU-2955
概率是浮点数，只能做值（而且这里是累乘，也不能化成整数），这里注意要化成安全概率（1-p[i]），求安全概率的最大值。
钱数作二层循环，最后用max取满足概率条件的最大值（再化回被抓概率）。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define IO ios::sync_with_stdio(false);cin.tie(0); 10 #define INF 1e9 11 typedef long long ll; 12 using namespace std; 13 int t, n, m[100010]; 14 double P, p[100010], dp[100010]; 15 int main() 16 { 17 IO; 18 cin >> t; 19 while(t--){ 20 cin >> P >> n; 21 int sum = 0; 22 memset(dp, 0, sizeof(dp)); 23 for(int i = 0; i < n; i++){ 24 cin >> m[i] >> p[i]; 25 sum += m[i]; 26 } 27 dp[0] = 1;//只要dp[0]=1即可，不是全置1 28 for(int i = 0; i < n; i++){ 29 for(int j = sum; j >= m[i]; j--){ 30 dp[j] = max(dp[j], dp[j-m[i]]*(1-p[i])); 31 } 32 } 33 int maxm=-INF; 34 for(int i = 0; i <= sum; i++){ 35 if(1-dp[i] <= P){ 36 maxm = max(i, maxm);//用max界定最大值最方便 37 } 38 } 39 cout << maxm << endl; 40 } 41 return 0; 42 }