题目描述

塔子哥有多种火药枪和有限的火药量。每种火药枪的威力、消耗的火药量和填充时间各不相同。你需要帮助塔子哥在规定的时间内或在火药耗尽之前，给予敌人最大的伤害。

题目思路

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); // 打印最大伤害
});