抢劫银行，WA40分 help me!!!

常规
1

7. 抢劫银行

题目ID：7158必做题100分

最新提交：

*Wrong Answer

40 分

历史最高：

Wrong Answer

40 分
*

时间限制: 1000ms

空间限制: 512000kB

题目描述

一个劫匪要去抢劫n家银行，每家银行有一定的现金，每抢一家银行该劫匪有一定几率被警察抓住，但是当该劫匪连续作案被抓住的几率小于p时他就可以逃脱，问该劫匪在不被捕的情况下最多能抢到多少钱？

输入格式

第一行为用例组数T，每组用例第一行为一个浮点数P和一个整数n分别表示被捕的几率上限以及该劫匪计划抢劫的银行数量，之后n行每行一个整数M和一个浮点数p表示该家银行的现金数以及该劫匪抢劫该家银行被捕的几率。

0<T≤1000<T≤100

0.0≤P≤1.00.0≤P≤1.0

0<n≤1000<n≤100

0≤Mj≤1000≤Mj​≤100

0.0≤pj≤1.00.0≤pj​≤1.0

输出格式

对于每组用例，输出该劫匪在不被捕的情况最多能抢到多少钱

样例

Input 1

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

Output 1

2 4 6

#include<bits/stdc++.h>
using namespace std;
int m[110];
double p[110];
double dp[10010];
int main(){
    int t;
    cin>>t;
    while(t--){
        double P;
        int n;
        cin>>P>>n;
        int sum=0;
        for(int i=1;i<=n;i++){
            cin>>m[i]>>p[i];
            sum+=m[i];
            p[i]=1.0-p[i];
        }
        fill(dp,dp+sum+1,0.0); 
        dp[0]=1.0;
        for(int i=1;i<=n;i++)
            for(int j=sum;j>=m[i];j--)
                if(dp[j-m[i]]>0)
                    dp[j]=max(dp[j],dp[j-m[i]]*p[i]);
        for(int j=sum;j>=0;j--){
        	if(dp[j]>=1.0-P){
                cout<<j<<endl;
                break;
            }
		}
    }
    return 0;
}
2 个赞
2

概率不好设到状态里面，我们考虑将钱设到状态里面。
状态表示：f[ x] 表示获得金钱为 x 时的成功逃脱概率
转移方程：f[ x]=max(f[ x],f[x-v[i]]*w[i]) 注意成功逃脱的概率是累乘
最后扫一遍看看逃脱概率大于等于 p 的金钱最多是多少就可以了。
核心代码：

        sum=0;
		memset(dp,0,sizeof(dp));
		cin>>p>>n;
		p=1-p;
        dp[0]=1;
		for(int i=1;i<=n;i++)
		{
			cin>>m>>t;
			t=1-t;
            sum+=m;
			for(int j=sum;j>=m;j--)
			{
				dp[j]=max(dp[j],dp[j-m]*t);
			}
		}
1 个赞
3

没听懂 :rolling_on_the_floor_laughing:

1 个赞
4

有两个地方错了

  • if (dp[j] >= (1.0 - P))

是 > 最多概率。

  • 如果没有可以抢的（不输出 j ）应该输出 0.
2 个赞
5

你6

6

这很无敌了。。。他是不是还在群里问了老师一遍？

7

是的