题目描述
一个劫匪要去抢劫n家银行，每家银行有一定的现金，每抢一家银行该劫匪有一定几率被警察抓住，但是当该劫匪连续作案被抓住的几率小于p时他就可以逃脱，问该劫匪在不被捕的情况下最多能抢到多少钱？
输入格式
第一行为用例组数T，每组用例第一行为一个浮点数P和一个整数n分别表示被捕的几率上限以及该劫匪计划抢劫的银行数量，之后n行每行一个整数M和一个浮点数p表示该家银行的现金数以及该劫匪抢劫该家银行被捕的几率。
0<T≤100
0.0≤P≤1.0
0<n≤100
0≤M j ≤100
0.0≤p j ≤1.0
输出格式
对于每组用例，输出该劫匪在不被捕的情况最多能抢到多少钱
样例
Input 1
3
0.04 3
1 0.02
2 0.03
3 0.05
0.06 3
2 0.03
2 0.03
3 0.05
0.10 3
1 0.03
2 0.02
3 0.05
Output 1
2
4
6
我的代码
#include <bits/stdc++.h>
using namespace std;
int t,m,C[10050];
double g[10005],dp[10005],p;
int main() {
int t,n;
cin>>t;
while(t--) {
cin>>p>>n;
int sum =0;
for(int i=1; i<=n; i++) {
cin >>C[i]>>g[i];
g[i]=1 -g[i];
sum +=C[i];
}
for(int i =1; i<=n; i++) {
for(int j=sum; j>=C[i]; j--) {
dp[j]=max(dp[j],dp[j-C[i]]*g[i]);
}
}
int f =0;
for(int i =sum; i >=0; i--) {
if(dp[i]>p) {
cout <<i<<endl;
f=1;
break;
}
}
if(f==0) {
cout<<0<<endl;
}
}
return 0;
}
