【筆記】DP：LIS 最長遞增子序列

【範例】ZeroJudge d242: 00481 – What Goes Up 【題解】

• a[ ]：讀入測資
• dp[ idx ]：掃描測資至 index-i 時的最長遞增子序列的長度
• v[ i ]：紀錄可位居第 i 順位的最小值 (讓後續數字有機會發展出更長的遞增子序列)。
• 【例子】a[ ] = {2, 1, 4, 3, 6, 7, 5}
  • i = 0, a[0] = 2, dp[0] = 1, v = {2}
  • i = 1, a[1] = 1 比 v.back( ) 小。找出 lower_bound(v.begin(), v.end(), a[1]) 的位置，將其置換為 a[1]。dp[1] = 1, v = {1}。
  • i = 2, a[2] = 4 比 v.back( ) 大，直接加進 v 的尾部。v = {1, 4}，dp[2] = 2 (此時最長遞增子序列的長度為2)。
  • i = 3, a[3] = 3 比 v.back( ) 小。找出 lower_bound(v.begin(), v.end(), a[3]) 的位置，將其置換為 a[3]。v = {1, 3}, dp[3] = 2。
  • i = 4, a[4] = 6 比 v.back( ) 大，直接加進 v 的尾部。v = {1, 3, 6}，dp[4] = 3 (此時最長遞增子序列的長度為3)。
  • i = 5, a[5] = 7 v.back( ) 大，直接加進 v 的尾部。v = {1, 3, 6, 7}，dp[5] = 4 (此時最長遞增子序列的長度為4)。
  • i = 6, a[6] = 5 比 v.back( ) 小。找出 lower_bound(v.begin(), v.end(), a[6]) 的位置，將其置換為 a[6]。v = {1, 3, 5, 7}, dp[6] = 3。
  • 最後 dp[ ] = {1, 1, 2, 2, 3, 4, 3}，最長遞增子序列的長度 = max(dp) = 4。
  • 由 dp，從後往前找出最長遞增子序列的值。
    • dp[5] = 4, ans = {7}
    • dp[4] = 3, ans = {7, 6}
    • dp[3] = 2, ans = {7, 6, 3}
    • dp[1] = 1, ans = {7, 6, 3, 1}
  • 逆序印出 ans，{1, 3, 6, 7} 即為最長遞增子序列。

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int num;
    vector<int> a;
    while (cin >> num){
        a.push_back(num);
    }
    int N = (int) a.size();
    int dp[N+1];
    vector<int> v;
    dp[0] = 1;
    v.push_back(a[0]);
    int L = 1; //LIS length
    for (int i=1; i<N; i++){
        if (a[i] > v.back()){
            v.push_back(a[i]);
            L++;
            dp[i] = L;
        } else {
            auto it = lower_bound(v.begin(), v.end(), a[i]);
            *it = a[i];
            dp[i] = (int) (it - v.begin() + 1);
        }
    }
    cout << L << "\n-\n";
    vector<int> ans;
    for (int i=N-1; i>=0; i--){
        if (dp[i] == L){
            ans.push_back(a[i]);
            L--;
        }
    }
    reverse(ans.begin(), ans.end());
    for (auto i: ans){
        cout << i << '\n';
    }
    return 0;
}

【更多練習】ZeroJudge d052: 11456 – Trainsorting 【題解】