题目大概是抢劫银行，每家银行都有一个收益和一个被抓的概率，求在被抓概率小于P的条件下能获得的最大收益。
- dp[i][j]表示抢劫前i家银行收益为j被抓的最小概率
- dp[0][0]=0
- dp[i][j]=min(dp[i-1][j],dp[i-1][j-m[i]]+(1-dp[i-1][j-m[i]])*p[i])
最后遍历一遍找答案就是了。
#include<cstdio>
#include<algorithm>
using namespace std;
double d[][];
int main(){
int t,n,x[];
double p,y[];
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
scanf("%lf%d",&p,&n);
int sum=;
for(int i=; i<=n; ++i){
scanf("%d%lf",x+i,y+i);
sum+=x[i];
}
for(int i=; i<=n; ++i){
for(int j=; j<=sum; ++j) d[i][j]=;
}
d[][]=;
for(int i=; i<=n; ++i){
for(int j=; j<=sum; ++j){
if(j>=x[i]) d[i][j]=min(d[i-][j],d[i-][j-x[i]]+(-d[i-][j-x[i]])*y[i]);
else d[i][j]=d[i-][j];
}
}
for(int i=sum; i>=; --i){
if(d[n][i]<p){
printf("Case %d: %d\n",cse,i);
break;
}
}
}
return ;
}