hdu2955（变形01背包）

时间：2023-03-08 17:35:54

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2955

分析：被抓概率可以转换成安全概率，Roy的安全概率大于1-P时都是安全的。

抢劫的金额为0时，肯定是安全的，所以dp[0]=1;其他金额初始为最危险的所以概率全为0；

#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define inf 1<<30

using namespace std;

int c[];

int n;

double p,dp[],w[];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lf%d",&p,&n);p=-p;

        int sum=;

        for(int i=;i<=n;i++)

        {

            scanf("%d%lf",&c[i],&w[i]);

            sum+=c[i];w[i]=-w[i];

        }

        memset(dp,,sizeof(dp));

        dp[]=;

        for(int i=;i<=n;i++)

            for(int j=sum;j>=c[i];j--)

            dp[j]=max(dp[j],dp[j-c[i]]*w[i]);

        for(int i=sum;i>=;i--)

        if(dp[i]>p)

        {

            printf("%d\n",i);

            break;

        }

    }

}

相关文章