这个题目起初是以为只是一个简单的01背包问题

结果发现错了

被抓住的概率是1-被抓住的概率

所以应该换一个dp的思路

f[j]=max(f[j],f[j-q[i].money]*q[i].v)   其中,f[j]表示抢j块大洋的最大的逃脱概率,条件是f[j-q[i].money]可达,也就是之前抢劫过;

#include
      
        #include
       
         typedef struct {
    int money; double v; }Bank; Bank bank[110]; int t,n; double p; double  dp[10010]; double max(double a,double b) {
    if(a>b) return a; else return b; } int main() {
    int i,j,sum;     scanf("%d",&t); while(t--)     {
            scanf("%lf%d",&p,&n); for(i=1,sum=0;i<=n;i++)         {
                scanf("%d%lf",&bank[i].money,&bank[i].v);             sum+=bank[i].money;         }         memset(dp,0,sizeof(dp));         dp[0]=1; for(i=1;i<=n;i++)         {
    for(j=sum;j>=bank[i].money;j--)             dp[j]=max(dp[j],dp[j-bank[i].money]*(1-bank[i].v));//dp[j]是逃跑率         } for(i=sum;i>=0;i--)         {
    if(dp[i]>=(1-p))//求最大的能偷到的数目             {
                    printf("%d\n",i); break;             }         }     } return 0; }