6. 小E的怪物挑战

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐中等

问题描述

1.小 E 可以击败血量和攻击力都小于她当前属性的怪物
2.对于每只怪物，小 E 可以选择与它战斗或者跳过这只怪物
3.为了保持战斗节奏，要求击败的怪物序列中，后一个怪物的血量和攻击力都必须严格大于前一个怪物

小 E 想知道，她最多能击败多少怪物。

**输入 **

• n：怪物的数量
• H：小 E 的血量
• A：小 E 的攻击力
• h[i]：第 i 个怪物的血量
• a[i]：第 i 个怪物的攻击力

**输出 **

• 返回小 E 最多能击败的怪物数量

**约束条件 **

• 1 < n < 100
• 1 < H,A,h[i],a[i] < 1000

测试样例

样例 1：

输入：n = 3, H = 4, A = 5, h = [1, 2, 3], a = [3, 2, 1]
输出：1

样例 2：

输入：n = 5, H = 10, A = 10, h = [6, 9, 12, 4, 7], a = [8, 9, 10, 2, 5]
输出：2

样例 3：

输入：n = 4, H = 20, A = 25, h = [10, 15, 18, 22], a = [12, 18, 20, 26]
输出：3

样例 4：

输入：n = 4, H = 20, A = 25, h = [22, 18, 15, 10], a = [26, 20, 18, 12]
输出： 1

解题思路

我们可以通过动态规划来解决这个问题。我们需要找到满足条件的怪物序列，使得每个怪物的血量和攻击力都严格大于前一个怪物，并且小 E 的血量和攻击力都大于当前怪物的血量和攻击力。

1. 问题理解：我们需要找到一个最长的怪物序列，使得每个怪物的血量和攻击力都严格大于前一个怪物，并且小 E 的血量和攻击力都大于当前怪物的血量和攻击力。
2. 数据结构选择：我们可以使用动态规划来解决这个问题。定义一个数组 dp，其中 dp[i] 表示以第 i 个怪物结尾的最长序列的长度。
3. 算法步骤：
   • 初始化 dp 数组，每个元素的初始值为 1，因为每个怪物本身可以构成一个长度为 1 的序列。
   • 对于每个怪物 i，遍历所有之前的怪物 j，如果怪物 i 的血量和攻击力都严格大于怪物 j，并且小 E 的血量和攻击力都大于怪物 i 的血量和攻击力，那么更新 dp[i] 为 dp[j] + 1。
   • 最终，dp 数组中的最大值就是我们要找的最长序列的长度。

开始解题

function solution(n, H, A, h, a) {
    // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
    // write code here
    let dp = new Array(n).fill(1); // 初始化 dp 数组，每个元素初始值为 1
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) { if (h[i] > h[j] && a[i] > a[j] && H > h[i] && A > a[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    
    return Math.max(...dp);
}

function main() {
    console.log(solution(3, 4, 5, [1, 2, 3], [3, 2, 1]) === 1);
    console.log(solution(5, 10, 10, [6, 9, 12, 4, 7], [8, 9, 10, 2, 5]) === 2);
    console.log(solution(4, 20, 25, [10, 15, 18, 22], [12, 18, 20, 26]) === 3);
}

main();

代码解释

• dp 数组用于存储以每个怪物结尾的最长序列的长度。
• 外层循环遍历每个怪物 i，内层循环遍历所有之前的怪物 j。
• 如果怪物 i 的血量和攻击力都严格大于怪物 j，并且小 E 的血量和攻击力都大于怪物 i 的血量和攻击力，那么更新 dp[i] 为 dp[j] + 1。
• 最终返回 dp 数组中的最大值，即最长序列的长度。

这个解法的时间复杂度为 O(n^2)，在给定的约束条件下是完全可以接受的。

以上关于6. 小E的怪物挑战的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。