Robberies （01背包dp变形）

题意：一个强盗要抢劫银行又不想被抓到，所以要进行概率分析求他在不被抓的情况下能抢最多的钱。他给定T（样例个数），N（要抢的银行的个数），P（被抓的概率要小于P）Mj（强盗能抢第j个银行Mj元钱），Pj（强盗抢第j个银行被抓的概率为Pj）。

思路：被抓的概率不好直接求出来，但可以直接求出不被抓的概率，则有状态转移方程dp[j] = max(dp[j], dp[j-b[i].money]*b[i].p)表示抢到j元钱被抓的最大的概率是多少。然后逆序遍历第一个小于P的dp的下标就是答案。

PS：数组的下标表示的是可以抢到的钱数，所以不能按100来开数组。。。。。。。。（T到吐血）

代码：

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#define INF 0x3f3f3f3f
#define FRE() freopen("in.txt","r",stdin)

using namespace std;
typedef long long ll;
const int maxn = 10000;
double dp[maxn];
struct Bank
{
    int money;
    double p;
} bb[maxn];

int main()
{
    ios::sync_with_stdio(false);
    int T,n;
    double p;
    cin>>T;
    while(T--)
    {
        int sum = 0;
        cin>>p>>n;
        for(int i = 0; i<n; i++)
        {
            cin>>bb[i].money>>bb[i].p;
            sum += bb[i].money;
        }
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        for(int i = 0; i<n; i++)
        {
            for(int j=sum; j>=bb[i].money; j--)
            {
                dp[j] = max(dp[j], dp[j-bb[i].money]*(1.0 - bb[i].p));
            }
        }
        int ans = 0;
        for(int i = sum; i>=0; i--)
        {
            if(1-dp[i]<=p)
            {
                ans = i;
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}