【筆記】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題解

分享本文 Share with friends