题解 | 小美打怪

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, h, a;
    while (cin >> n >> h >> a) {
        vector<pair<int, int>> m(n); //monster<h,a>
        vector<int> dp(n); //dp[i]为到i号怪物的总击败的数量
        for (int i = 0; i < n; ++i)
            cin >> m[i].first;
        for (int j = 0; j < n; ++j) {
            cin >> m[j].second;
        }
        sort(m.begin(), m.end());//怪物按h升序，同一h,按a升序
        for (int i = 0; i < n; ++i) {
            if (m[i].first >= h || m[i].second >= a)
                dp[i] = -1; //为-1代表不能打败
            else
                dp[i] = 1;
        }

        for (int i = 0; i < n; ++i) {
            if (dp[i] == -1)
                continue;
            for (int j = 0; j < i; ++j) {
                if (dp[j] == -1) continue;
                if (m[i].first > m[j].first && m[i].second > m[j].second)
                    dp[i] =  max(dp[i], dp[j] + 1);
            }
        }

        int cnt = 0;
        for  (int k = 0; k < n; ++k) {
            cnt = max(dp[k], cnt);
        }
        cout << cnt;
    }

    return 0;
}