3636 - 偷银行
有个小偷研究了几个月了，他一直在评估各银行的安全和现金持有量。他想做一个计算风险，并抓住尽可能多的
钱。每个银行最多只可以被偷一次。可是他偷每家银行总是有一定的概率被抓，现在给了你一个概率P，只要他
被抓的概率乘积不大与P，他就是安全的。
Input
有多组数据，输入的第一行给出了T，（T个情况）。对于每一个情况下，输入的第一行给出一个浮点数P，和一
个整数n，n为计划的银行数量。接下来n行，其中给出了一个整数PJ（钱数）MJ（被抓概率）。
注：0 < T <= 10
0.0 <= P <= 1.0
0 < N <= 10
0 < Pj <= 10
0.0 <= Mj <= 1.0
</p>
Output
对于每个测试用例，输出他可以在安全的情况下，并偷到的最大钱数
Examples
Input
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 2 0.04 2 1 0.02 3 0.02 0.05 2 1 0.02 2 0.03
Output
2 4 6 4 3
Solution C++
#include<stdio.h> #include<string.h> #define N 105 double w[N]; int v[N]; double dp[10005];//抢i元不被抓的最大概率 double Max(double a,double b) { if(a>b) return a; else return b; } int main() { int i,j; //freopen("test.txt","r",stdin); //freopen("test.out","w",stdout); int T; while(scanf("%d",&T)!=EOF) { for(i=0;i<10005;i++) { dp[i]=0; } while(T--) { double vt; int n; int i,j; scanf("%lf%d",&vt,&n); int sum=0; for(i=0;i<n;i++) { scanf("%d%lf",&v[i],&w[i]); sum+=v[i]; w[i]=1-w[i]; } for(i=0;i<=sum;i++) dp[i]=0; dp[0]=1; //偷0元钱不被抓的概率肯定为1了，，， for(i=0;i<n;i++) { for(j=sum;j>=v[i];j--) dp[j]=Max(dp[j],dp[j-v[i]]*w[i]); } vt=1-vt; //不被抓的最小概率 for(i=sum;i>=0;i--) { if(dp[i]>vt) { printf("%d\n",i); break; } } } } return 0; }