小E的怪物挑战

问题描述

小E在一个游戏中遇到了 n 个按顺序出现的怪物。每个怪物都有其特定的血量h[i]和攻击力a[i]。小E的初始血量为 H， 攻击力为 A。

游戏规则如下：

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

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

1. 输入

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

2. 输出

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

3. 约束条件

   • 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

解题思路

1. 初始化：创建一个动态规划数组 dp，其中 dp[i] 表示以第 i 个怪物结尾的最长严格递增子序列的长度。
2. 状态转移：对于每个怪物 i，遍历之前的所有怪物 j，如果怪物 j 的血量和攻击力都小于怪物 i，则更新 dp[i]。
3. 结果：最终结果是 dp 数组中的最大值。

代码实现

Cangjie

func solution(
    n: Int64,
    H: Int64,
    A: Int64,
    h: Array<Int64>,
    a: Array<Int64>
) {
    var cnt = 0;
    let dp = Array<Int64>(n, repeat: 0);
    for (i in 0..n) {
        if (H > h[i] && A > a[i]) {
            dp[i] = 1
            for (j in 0..i) {
                if (h[j] < h[i] && a[j] < a[i]) {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            cnt = max(dp[i], cnt)
        }
    }
    cnt
}

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

Rust

fn solution(
    n: i32, 
    h: i32, 
    a: i32, 
    heights: Vec<i32>, 
    ages: Vec<i32>
) -> i32 {
    let mut cnt = 0;
    let mut dp = vec![0; n as usize];
    for i in 0..n {
        if h > heights[i as usize] && a > ages[i as usize] {
            dp[i as usize] = 1;
            for j in 0..i {
                if heights[j as usize] < heights[i as usize] 
                    && ages[j as usize] < ages[i as usize] {
                    dp[i as usize] = dp[i as usize].max(dp[j as usize] + 1);
                }
            }
            cnt = cnt.max(dp[i as usize]);
        }
    }
    cnt
}

fn main() {
   println!("{}", solution(3, 4, 5, vec![1, 2, 3], vec![3, 2, 1]) == 1);
   println!("{}", solution(5, 10, 10, vec![6, 9, 12, 4, 7], vec![8, 9, 10, 2, 5]) == 2);
   println!("{}", solution(4, 20, 25, vec![10, 15, 18, 22], vec![12, 18, 20, 26]) == 3);
}

Python

def solution(n: int, H: int, A: int, h: list, a: list) -> int:
    cnt = 0
    dp = {}
    for i in range(n):
        if H > h[i] and A > a[i]:
            dp[i] = 1
            for j in range(i):
                if h[j] < h[i] and a[j] < a[i]:
                    dp[i] = max(dp[i], dp[j]+1)

            cnt = max(dp[i], cnt)

    return cnt

print(solution(3, 4, 5, [1, 2, 3], [3, 2, 1]) == 1)
print(solution(5, 10, 10, [6, 9, 12, 4, 7], [8, 9, 10, 2, 5]) == 2)
print(solution(4, 20, 25, [10, 15, 18, 22], [12, 18, 20, 26]) == 3)

JavaScript

function solution(n, H, A, h, a) {
    let cnt = 0;
    let dp = {};
    for (let i = 0; i < n; i++) {
        if (H > h[i] && A > a[i]) {
            dp[i] = 1;
            for (let j = 0; j < i; j++) {
                if (h[j] < h[i] && a[j] < a[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            cnt = Math.max(dp[i], cnt);
        }
    }
    return cnt;
}

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);

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为数组的长度。
• 空间复杂度：O(n)，其中 n为数组的长度。