对于这题来说,我们把钱的总和当做背包的容量,然后递减地更新每次的逃跑概率就行了。
对于数据范围,题上说的是每个银行最多有100万,最多有100家银行,所以我们就要开
一个10000的数据范围,不然就超时,因为我们是一位数组,节省空间,所以就要开这么大。
而且,题中给的是被抓概率,所以我们要减一换算成逃跑的概率,每次的逃跑概率因为是独立的,
所以就是他们的乘积就对了。
#include <iostream> #include <cstring> using namespace std; int m[10000], T, N, sum; double p[10000], P, ans[10000]; int main() { ios::sync_with_stdio(false); cin >> T; while (T--) { cin >> P >> N; sum = 0; memset(ans, 0, sizeof(ans)); ans[0] = 1; for (int i = 0; i < N;i++) { cin >> m[i] >> p[i]; sum += m[i]; } for (int i = 0; i < N;i++) { for (int j = sum; j >= m[i];j--) {//在背包容量范围内 ans[j] = max(ans[j], ans[j - m[i]] * (1 - p[i])); //对于每个容量(抢的钱数)抢或者不抢两种情况,进行逃跑概率的更新 } } for (int i = sum; i >= 0;i--) { if (ans[i]>(1-P)) {//抢钱越多,逃跑的概率越小 cout << i << endl; break; } } } return 0; }