我有两题，解出必有解决方案

问题讨论区 基础段
1

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

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

0<T≤100
0.0≤P≤1.0
0<n≤100
0≤M j≤100
0.0≤p j≤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
第二题
题目描述
【版权说明】

本题为改编题。

【问题描述】

愚公移山的故事相信大家都听过，愚公日复一日的劳作，终于还需要再搬走至少体积为 m 的石头这条路就畅通了，已知每块的体积和把它移走需要的体力分别为 v i和 w i。愚公已经移山移了这么长时间了，他也很累了，他还剩下的体力为c。
输入格式
输入文件的第一行是三个整数：m、n、c。(1≤m,n,c≤10000)

接下来 n 行，每行两个整数：分别为每块石头的体积 v i和移走需要的体力 w i。(1≤v i​ ,w i≤1000)

输出格式
输出文件只有一行，如果愚公能把山移完，则输出他把山移完剩下的最大的体力，否则输出 “Impossible”（不带引号）。

输入输出样例
输入 #1

100 2 10
50 5
50 5
输出 #1

0
输入 #2

10 2 1
50 5
10 2
输出 #2

Impossible

2

T2：

dp[j]:当前体力下能搬动的最大体积
状态转移：dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

  答案：
  i=1->c
      if(dp[i]>=m) ans=min(ans,i)//如果没有大于等于过就不可能
  if(/*大于过*/) cout << c-ans;
  else cout << "Impossible";

自认为十分的详细

4

T2
我还不会
我的代码

#include<bits/stdc++.h>
using namespace std;
int w[1005],v[1005],dp[1005],ans;
int main(){
	int m,n,c;
	cin>>m>>n>>c;
	for(int i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=c;j>=w[i];j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	for(int i=1;i<=c;i++){
		if(dp[i]>=m) ans=max(ans,i);
	}
	if(c-ans>=0) cout << c-ans;
	else cout << "Impossible";
	return 0;
}
5

w和v写反了 :slightly_smiling_face:

6

还是20分

7

不好意思这里是min

8

变0分了

批注 2024-08-16 144758
批注 2024-08-16 144758745×486 22.5 KB

9

你取最小值，ans一开始得1e9啊

10

所以你T1会吗

11

不会