#include <bits/stdc++.h>
using namespace std;
int mei_0,mei_1;//小美的生命值和攻击力

bool cmp(const pair<int,int>& a,const pair<int,int>& b){
    if(a.first==b.first)return a.second<b.second;
    return a.first<b.first;
}//生命值升序，相同生命值攻击力升序

bool cmpp(const pair<int,int>& a,const pair<int,int>& b){
    if(a.first==b.first)return a.second>b.second;
    return a.first<b.first;
}//生命值升序，相同生命值攻击力降序
/*
LOS_dp为dp解法，n方的复杂度，对于cmp排序法和cmpp排序法均可
*/
void LOS_dp(vector<pair<int,int>>&v){
    int n=v.size();
    vector<int>dp(n,1);
    for(int i=1;i<n;i++){
        if(v[i].second>mei_1){//攻击力大于小美则直接非法
            dp[i]=-1e9;
            continue;
        }
        for(int j=i-1;j>=0;j--){
            if(v[i].second>v[j].second&&v[i].first!=v[j].first){//生命值不能相同，相同直接过
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
    }
    int ans=*max_element(dp.begin(),dp.end());
    
    cout<<(ans<0?0:ans);
}
/*
LOS_nlogn是贪心+二分的解法，nlogn的复杂度，但是只能使用cmpp排序法，因为在相同血量的情况下：大攻击力先进行添加，后再添加小攻击力绝对会添加在前者的前面，则不会影响到整体的数量，所以必须采取cmpp排序法
*/
void LOS_nlogn(vector<pair<int,int>>&v){
    vector<int>tails;
    int n=v.size();
    for(int i=0;i<n;i++){
        int atk=v[i].second;
        if(atk>=mei_1)continue;//攻击力大于小美则非法
        auto it=lower_bound(tails.begin(),tails.end(),atk);
        if(it==tails.end()){
            tails.emplace_back(atk);
        }
        else *it=atk;
    }
    cout<<tails.size();
}
int main() {
    int n;cin>>n;
    vector<pair<int,int>>v(n);

    cin>>mei_0>>mei_1;
    for(int i=0;i<n;i++){
        cin>>v[i].first;
    }
    for(int i=0;i<n;i++){
        cin>>v[i].second;
    }
    // sort(v.begin(),v.end(),cmp);
    sort(v.begin(),v.end(),cmpp);

    auto it=upper_bound(v.begin(), v.end(),make_pair(mei_0,mei_1),cmp);//删除掉全部生命值大于小美的
    v.erase(it,v.end());
    if(v.size()==0){//防越界特判
        cout<<0;
        return 0;
    }
    
    LOS_dp(v);
    // LOS_nlogn(v);
    return 0;
}

这是一道经典的最长上升子序列 (LIS) 变种问题。核心在于理解“打怪升级”的规则，并选择合适的算法优化。

问题简述

  • 小美属性：拥有生命值 mei_0 和攻击力 mei_1。
  • 怪物属性：每只怪有生命值 v[i].first 和攻击力 v[i].second。
  • 战斗规则： 小美只能打攻击力严格小于自己 (atk < mei_1) 的怪。打怪后，小美的属性会变成该怪物的属性。关键限制：如果两只怪生命值相同，只能选其中一只（因为打完一只后，属性变了，无法再打同生命值但不同攻击力的另一只）。

解题思路

1. 数据预处理

首先，我们需要筛选出所有能打得过的怪物：

  • 攻击力限制：怪物攻击力必须小于 mei_1。
  • 生命值限制：怪物生命值必须小于等于 mei_0（利用 upper_bound 进行二分删除）。

2. 核心算法选择

有两种解法：

  • 解法一：DP ()适用场景：数据量较小时。状态转移：dp[i] = max(dp[j] + 1，dp[i])，其中 j < i 且 v[i].second > v[j].second 且 v[i].first != v[j].first。排序：使用 cmp（生命值升序，同生命值攻击力升序）。
  • 解法二：贪心 + 二分 ()适用场景：数据量较大时（推荐）。核心思想：维护一个 tails 数组，tails[i] 代表长度为 i+1 的上升子序列的最小尾部攻击力。关键排序：必须使用 cmpp（生命值升序，同生命值攻击力降序）。 为什么要降序？ 这样在处理同生命值的一组怪时，会先处理攻击力大的。由于二分查找 (lower_bound) 的特性，攻击力小的会覆盖掉攻击力大的在 tails 中的位置，从而保证同生命值下只保留最优（攻击力最小）的那个状态，且不会增加序列长