HDU2955 01背包变体 xingxing在努力

　　这道题的题意是小偷要去偷N家银行，每家银行都有一个钱款数额Mi和被抓概率pi, 求小偷被抓的概率小于P的情况下所能偷到的钱数额的最大值（每家银行最多偷一次），由于每家银行最多偷一次，所以这个题可以用01背包的思想来求解，又因为小偷被抓会有很多种情况，并不好算，因此我们用他的反面小偷成功逃脱来算？这样题目就成了小偷在成功逃脱的概率大于1-P的情况下所能偷到的钱数最大值。。记f[i][j]为小偷在前i家银行恰好偷了j块钱成功逃脱的概率最大值，那么f[i][j] = max(f[i-1][j], f[i-1][j-W[i]]*(1-Pi[i])),该过程可以使滚动数组优化：代码如下：

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const double inf = 100000000000000;
const double eps = 1e-12;
int Mi[100 + 10];
double Pi[100 + 10];
double f[10000 + 100];
double P;
int N;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lf%d", &P, &N);
        P = 1 - P;
        int sum = 0;
        for(int i=1; i<=N; i++)
        {
            scanf("%d%lf", &Mi[i], &Pi[i]);
            sum += Mi[i];
        }
        for(int i=1; i<=sum; i++) f[i] = -inf;
        f[0] = 1;    //刚开始抢了0家银行， 逃脱概率为1
        int res = 0;
        for(int i=1; i<=N; i++)
        {
            for(int j=sum; j>=Mi[i]; j--)
            {
                f[j] = max(f[j], f[j-Mi[i]]*(1-Pi[i]));
                if(f[j]-P >= 0)
                    res = max(res, j);
            }
        }
        printf("%d
", res);
    }
    return 0;
}

HDU2955 01背包变体 xingxing在努力

相关推荐