题解 | 小美打怪

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 5;
struct M {
    ll h = 0; // 怪物血量
    ll a = 0; // 怪物攻击力
};

M m[N];


int main() {
    ll n, H, A;
    // 算法辅助：关闭C++标准输入输出同步，解绑cin与cout，加快输入速度（应对大规模测试数据）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // 读取输入：怪物数量n，小美初始血量H、初始攻击力A
    if (!(cin >> n >> H >> A)) return 0;

    // 读取所有怪物的血量
    for (ll i = 1; i <= n; i++) {
        cin >> m[i].h;
    }
    // 读取所有怪物的攻击力
    for (ll i = 1; i <= n; i++) {
        cin >> m[i].a;
    }

    // ===================== 算法步骤1：初始筛选（核心预处理） =====================
    // 思想：小美后续属性只会降级，无法击败初始条件不满足的怪物，因此先筛选出「一开始就能击败」的怪物
    // 筛选条件：怪物血量 < 小美初始血量 且 怪物攻击力 < 小美初始攻击力
    M t[N]; // 存储筛选后的有效怪物（仅保留初始可击败的）
    ll k = 1; // 有效怪物的计数指针（t数组从1开始存储，k最终为有效怪物数+1）
    for (ll i = 1; i <= n; i++) {
        if (m[i].h < H&& m[i].a < A) {
            t[k] = m[i]; // 存入有效怪物数组
            k++;
        }
    }

    // ===================== 算法步骤2：边界条件判断 =====================
    // 思想：若k==1，说明没有符合初始筛选条件的怪物（t数组无有效数据），直接输出0
    if (k == 1) {
        cout << 0;
        return 0;
    }

    // ===================== 算法步骤3：排序（为动态规划铺垫） =====================
    // 思想：按怪物血量h降序排序，血量相同则按攻击力a降序排序
    // 目的：将双属性约束问题转化为有序序列问题，便于后续动态规划寻找「可连续击败」的怪物序列
    sort(t + 1, t + k, [](M x, M y) {
        if (x.h != y.h) return x.h > y.h; // 第一关键字：血量降序
        return x.a > y.a; // 第二关键字：攻击力降序
        });

    // ===================== 算法步骤4：动态规划（DP）求解最大击败数量（核心算法） =====================
    // 1. DP数组定义：dp[j] 表示以第j个怪物（t[j]）结尾时，能击败的最大怪物数量
    // 初始化：每个怪物单独击败时，数量都为1，因此dp数组初始值全为1
    vector<ll> dp(k, 1);
    ll cnt = 1; // 记录全局最大击败数量，初始为1（至少能击败1个有效怪物）

    // 2. 状态转移：两层循环遍历所有有效怪物，寻找可连续击败的序列
    // 外层循环：遍历每个作为「前一个击败怪物」的候选（i从1到k-1）
    //因为数组已经过相应排序，此时该下降链动态规划中某一状态由在其之前所有的状态遍历决定
    for (ll i = 1; i <= k - 1; i++) {
        // 内层循环：遍历每个作为「后一个击败怪物」的候选（j从i+1到k-1）
        for (ll j = i + 1; j <= k - 1; j++) {
            // 状态转移条件：前一个怪物t[i]的双属性都大于后一个怪物t[j]
            // 对应逻辑：小美击败t[i]后，属性更新为t[i].h和t[i].a，仍能击败t[j]
            if (t[i].h > t[j].h && t[i].a > t[j].a) {
                // 状态转移方程：dp[j] = max(当前dp[j], dp[i]+1)
                // 含义：以t[j]结尾的最大击败数量，要么保持原有值，要么继承t[i]的结果+1（击败t[j]）
                dp[j] = max(dp[j], dp[i] + 1);
                // 更新全局最大击败数量
                cnt = max(cnt, dp[j]);
            }
        }
    }

    // ===================== 算法步骤5：输出结果 =====================
    // 输出全局最大击败数量，即最长可连续击败的怪物序列长度
    cout << cnt;
    return 0;
}