Chokudai SpeedRun 002 L - 長方形 β (600 点)

面白かった

問題へのリンク

問題概要

個の長方形がある。各辺の長さは整数値である。
この長方形から何個か選んでマトリョーシカを作りたい。最大で何重にできるか？
長方形の縦と横をひっくり返してもよい。

制約

• 

考えたこと

もし長方形が縦横ひっくり返すのが禁止だったら、単純な LIS (Longest Increasing Subsequence) になることは有名問題である。

実は長方形の縦横ひっくり返すことを許容しても、結局 個の長方形のマトリョーシカになる。なぜなら

• 
• 

とはマトリョーシカにおいて同時に選ばれることはない。なお、実際に LIS にするときに、

• が小さい順にソートする
• が等しいところについては が大きい順にソートする

とするのが常套手段な感じ。こうすることで が等しいような長方形が 2 個以上選ばれることを最初から防ぐことができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;

template<class T> int LIS(vector<T> a,  bool is_strong = true) {
    const T INF = 1<<30; // to be set appropriately
    int n = (int)a.size();
    vector<T> dp(n, INF);
    for (int i = 0; i < n; ++i) {
        if (is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

int main() {
    int N; cin >> N;
    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];

    vector<pint> v;
    for (int i = 0; i < N; ++i) {
        v.push_back(pint(A[i], -B[i]));
        v.push_back(pint(B[i], -A[i]));
    }
    sort(v.begin(), v.end());
    vector<int> vec;
    for (int i = 0; i < v.size(); ++i) vec.push_back(-v[i].second);
    cout << LIS(vec) << endl;
}