#P1582. 2022.11.09-秋招-攻城战
-
ID: 15
Tried: 85
Accepted: 19
Difficulty: 7
2022.11.09-秋招-攻城战
题目内容
现在小红有火药枪若干， 以及数量有限的火药，每种火药枪的威力不尽相同，且在每次开火之前都需要一定时间填充火药， 请你帮助小红在给定的时间结束之前或者火药存量耗尽之前给予敌人最大的伤害。
限制:
- 火药枪每次开火的威力一样；
- 火药剩余量不小于火药枪的消耗量，该火药枪才能开火；
- 填充火药之外的时间忽略不计；
- 不同种火药枪可以同时开火。
输入描述
第一行，整数 N ， M ， T ， N 表示火药枪种类个数， M 表示火药数量， T 表示攻城时间，1≤N,M,T≤1000。
接下来 N 行，每一行三个整数 A ， B ， C 。分别表示火药枪的威力，火药枪每次攻击消耗的火药量，火药枪每次攻击填充火药的时间，0≤A,B,C≤100000。
输出描述
输出在给定的时间结束之前或者火药存量耗尽之前给予敌人最大的伤害。
样例
样例一：
输入
3 88 30
10 7 5
5 3 1
4 4 8
输出
145
样例解释
总共有 3 种火药枪，火药存量 88 ， 攻城时间 30 ;
第 1 种火药枪威力 10 ，每次攻击消耗火药 7 ，每次攻击填充火药时间 5 ；
第 2 种火药枪威力 5 ，每次攻击消耗火药 3 ，每次攻击填充火药时间 1 ；
第 3 种火药枪威力 4 ，每次攻击消耗火药 4 ，每次攻击填充火药时间 8 ；
样例二：
输入
2 10 15
2 2 2
3 3 3
输出
10
样例解释
总共有 2 种火药枪，火药存量 10 ，攻城时间 15 ；
第 1 种火药枪威力 2 ，每次攻击消耗火药 2 ，每次攻击填充火药时间 2 ；
第 2 种火药枪威力 3 ，每次攻击消耗火药 3 ，每次攻击填充火药时间 3 ；
题目描述
塔子哥有多种火药枪和有限的火药量。每种火药枪的威力、消耗的火药量和填充时间各不相同。你需要帮助塔子哥在规定的时间内或在火药耗尽之前，给予敌人最大的伤害。
题目思路
1.理解问题：
每种火药枪的威力是固定的，每次开火消耗一定量的火药，并且在每次开火之前需要一定的填充时间。 不同种火药枪可以同时开火。
2.转换为多重背包问题：
每种火药枪可以看作一种物品，威力是价值，消耗的火药量是物品的体积，填充时间限制了每种火药枪的使用次数。 对于每种火药枪，可以发射的次数为 min(M // B[i], T // C[i])，这里 B[i] 是消耗的火药量，C[i] 是填充时间。
3.动态规划：
使用动态规划数组 dp，其中 dp[j] 表示使用 j 量火药所能达到的最大伤害。 通过迭代所有火药枪和可能的火药消耗量，更新最大伤害值。
代码说明
1.输入读取：
读取火药枪的种类数量 N，火药总量 M，以及攻城时间 T。 接下来，读取每种火药枪的威力、消耗的火药量和填充时间。
2.初始化变量：
创建一个数组 dp，大小为 M + 1，用来记录不同火药消耗下的最大伤害。
3.构建动态规划逻辑：
遍历每种火药枪，计算该火药枪能开火的最大次数。 使用倒序遍历更新 dp 数组，确保每种火药枪的使用次数不会重复。 输出结果：
最后，输出 dp 数组的最大值，即为在给定条件下能造成的最大伤害。
代码
Python代码
n, m, T = map(int, input().split())
A, B, C = [], [], []
for i in range(n):
a, b, c = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
dp = [0]*(m+1) # dp初始化为0
for i in range(n): # 枚举大炮
for j in range(m, -1, -1): # 倒序遍历使得一个大炮不能重复更新
mx = min((m-j)//B[i], T//C[i]) # 计算当前的大炮最多发射几下
for k in range(1, mx+1): # 枚举当前的第i门大炮发射几下
dp[j+k*B[i]] = max(dp[j+k*B[i]], dp[j]+k*A[i])
print(max(dp)) # 输出最大值
C++代码
#include <iostream>
using namespace std;
// 定义数组，存储火药枪的威力、消耗火药量和填充时间
int a[1005], b[1005], c[1005];
int dp[10004]; // 动态规划数组，存储不同火药消耗下的最大伤害
int main() {
int n, m, T; // n: 火药枪种类数, m: 火药总量, T: 攻城时间
cin >> n >> m >> T; // 读取火药枪种类、火药总量和攻城时间
// 读取每种火药枪的威力、消耗火药量和填充时间
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i] >> c[i];
// 动态规划处理
for (int i = 0; i < n; i++) { // 遍历每种火药枪
for (int j = m; j >= 0; j--) { // 倒序遍历火药量
// 计算当前火药枪最多能发射的次数
int mx = min((m - j) / b[i], T / c[i]);
for (int k = 1; k <= mx; k++) { // 遍历当前火药枪能发射的次数
// 更新动态规划数组，确保不超过总火药量
if (j + k * b[i] <= m) {
dp[j + k * b[i]] = max(dp[j + k * b[i]], dp[j] + k * a[i]); // 更新最大伤害
}
}
}
}
// 找到最大伤害
int ans = 0;
for (int i = 0; i <= m; i++) // 遍历所有可能的火药消耗量
ans = max(ans, dp[i]); // 更新最大伤害
cout << ans << endl; // 输出结果
return 0; // 程序结束
}
Java代码
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); // 创建扫描器对象以读取输入
int n = scanner.nextInt(); // 火药枪种类数
int m = scanner.nextInt(); // 火药总量
int t = scanner.nextInt(); // 攻城时间
// 定义数组来存储每种火药枪的威力、消耗火药量和填充时间
int[] a = new int[n]; // 威力
int[] b = new int[n]; // 消耗的火药量
int[] c = new int[n]; // 填充时间
// 读取每种火药枪的信息
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt(); // 读取威力
b[i] = scanner.nextInt(); // 读取消耗的火药量
c[i] = scanner.nextInt(); // 读取填充时间
}
// 初始化动态规划数组，大小为 m + 1
int[] dp = new int[m + 1];
// 动态规划处理
for (int i = 0; i < n; i++) { // 遍历每种火药枪
for (int j = m; j >= 0; j--) { // 倒序遍历剩余的火药量
// 计算当前火药枪最多能发射的次数
int mx = Math.min((m - j) / b[i], t / c[i]);
// 遍历当前火药枪能发射的次数
for (int k = 1; k <= mx; k++) {
// 更新动态规划数组，确保不超过总火药量
dp[j + k * b[i]] = Math.max(dp[j + k * b[i]], dp[j] + k * a[i]);
}
}
}
// 找到最大伤害
int ans = 0; // 初始化最大伤害为0
for (int i = 0; i <= m; i++) // 遍历所有可能的火药消耗量
ans = Math.max(ans, dp[i]); // 更新最大伤害
// 输出结果
System.out.println(ans); // 打印最大伤害
}
}
Js代码
// 使输入流保持活动状态并设置编码
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = ''; // 初始化输入字符串
// 监听输入数据事件，将数据追加到 input 字符串
process.stdin.on('data', (data) => {
input += data;
return;
});
// 监听输入结束事件
process.stdin.on('end', () => {
// 将输入数据按行分割
input = input.split('\n');
// 读取火药枪的种类数 n，火药总量 m 和攻城时间 t
let n = Number(input[0].split(' ')[0]);
let m = Number(input[0].split(' ')[1]);
let t = Number(input[0].split(' ')[2]);
// 初始化存储威力、消耗的火药量和填充时间的数组
let a = new Array(n).fill(0); // 威力数组
let b = new Array(n).fill(0); // 消耗的火药量数组
let c = new Array(n).fill(0); // 填充时间数组
let dp = new Array(m + 1).fill(0); // 动态规划数组，大小为 m + 1
// 读取每种火药枪的信息
for (let i = 0; i < n; i++) {
a[i] = Number(input[i + 1].split(' ')[0]); // 读取威力
b[i] = Number(input[i + 1].split(' ')[1]); // 读取消耗的火药量
c[i] = Number(input[i + 1].split(' ')[2]); // 读取填充时间
}
// 动态规划处理
for (let i = 0; i < n; i++) { // 遍历每种火药枪
for (let j = m; j >= 0; j--) { // 倒序遍历剩余的火药量
// 计算当前火药枪最多能发射的次数
let mx = Math.min(parseInt((m - j) / b[i]), parseInt(t / c[i]));
// 遍历当前火药枪能发射的次数
for (let k = 1; k <= mx; k++) {
// 更新动态规划数组，确保不超过总火药量
dp[j + k * b[i]] = Math.max(dp[j + k * b[i]], dp[j] + k * a[i]);
}
}
}
// 找到最大伤害
let ans = 0; // 初始化最大伤害为0
for (let i = 0; i <= m; i++) // 遍历所有可能的火药消耗量
ans = Math.max(ans, dp[i]); // 更新最大伤害
// 输出结果
console.log(ans); // 打印最大伤害
});