【題解】POJ 2533 Longest Ordered Subsequence

【題目敘述】https://vjudge.net/problem/POJ-2533
【解題想法】LIS 模板題

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    int a[N], dp[N];

    for (int i=0; i<N; i++){
        cin >> a[i];
    }
    memset(dp, 0, sizeof(dp));
    vector <int> v;
    v.push_back(a[0]);
    int LIS = 1;
    dp[0] = 1;
    for (int i=1; i<N; i++){
        if (a[i] > v.back()){
            v.push_back(a[i]);
            dp[i] = ++LIS;
        } else {
            //POJ does not accept "auto"
            vector<int>::iterator it = lower_bound(v.begin(), v.end(), a[i]);
            *it = a[i];
            dp[i] = (int)(it - v.begin() + 1);
        }
    }
    cout << LIS << '\n';
    return 0;
}
分享本文 Share with friends