Problem B: 爱恨此消彼长

📝 题目描述

🔑 算法模块

快速枚举/深搜

💡 思路分析

不难发现数据范围很小，可以借助二进制暴力枚举所有情况。取所有情况的最大值即可。

🖥️ 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll n, ans = 0;
    cin >> n;
    vector<pair<ll, ll>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    for (int i = 0; i < (1 << n); i++) {
        vector<ll> b;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                b.push_back(a[j].second);
            } else {
                b.push_back(a[j].first);
            }
        }
        ll cur = 0, cnt = 0;
        for (ll val : b) {
            if (val > cur) {
                cnt++;
                cur = val;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << "\n";
    return 0;
}

⏱️ 复杂度分析

📚 拓展