verify/aoj/aoj_dpl_1_d.test.cpp

• View this file on GitHub
• Last update: 2024-06-25 09:33:29+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D

Depends on

• dp/longest_increasing_subsequence.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"

#include <bits/stdc++.h>
using namespace std;

#include "../../dp/longest_increasing_subsequence.hpp"

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cout << longest_increasing_subsequence<int>(A) << endl;

    return 0;
}

#line 1 "verify/aoj/aoj_dpl_1_d.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D"

#include <bits/stdc++.h>
using namespace std;

#line 1 "dp/longest_increasing_subsequence.hpp"
template<class T>
int longest_increasing_subsequence(const vector<T> &A) {
    vector<T> lis;
    for(const auto& p : A) {
        // 狭義
        auto it = lower_bound(lis.begin(), lis.end(), p);
        if(lis.end() == it) lis.push_back(p);
        else *it = p;
    }
    return lis.size();
}
#line 7 "verify/aoj/aoj_dpl_1_d.test.cpp"

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cout << longest_increasing_subsequence<int>(A) << endl;

    return 0;
}

Back to top page