題目： UVa - 481 - What Goes Up

題目說明

依序給一些數字，找出這些數字的最長嚴格遞增子序列 ( Longest Increasing Subsequence ) 長度及最長嚴格遞增子序列。若有相同長度的 LIS 的話，以選擇後面的元素的 LIS 優先。

Input： 只有一組測資，每行一個整數直到 EOF。

Output： 輸出最長嚴格遞增子序列長度及最長嚴格遞增子序列。

解題思路

基本的 LIS 題目，直接讀取數字同時處理，與先讀取後遍歷陣列的意思相同。

每次讀取 nums[i] 後，先在 seq[] 中找到一個最接近且大於等於 nums[i] 的數，並取得其位置 pos，意義為以 nums[i] 做結尾的 LIS 的最大長度為 pos + 1，L 表示目前能夠找到的最大 LIS 長度，因此若 pos == L，表示以 nums[i] 做結尾的 LIS 是目前能夠找到的 LIS 最大長度，因此更新 lastIdx，由於題目要求，若 pos == L - 1 即以 nums[i] 結尾的 LIS 與目前能找到的最長 LIS 的長度相同，因此也要更新 lastIdx。同時維護 id[] 及 pre[] 最後才能輸出 LIS。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;

// reference: https://ppt.cc/fDPncx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

const int N = (int)1e6;

int L;
int lastIdx; // 最長的 LIS 中的最後一個元素的 index
int nums[N];
int seq[N];
int id[N];   // seq[] 中相應位置元素的 index，即若 seq[0] = nums[5]，id[0] = 5
int pre[N];  // pre[i] 表包含 nums[i] 的 LIS，位於 nums[i] 的前一個元素在 nums[] 中的 index

void LIS()
{
    for (int i = 0; cin >> nums[i]; ++i)
    {
        int pos = lower_bound(seq, seq + L, nums[i]) - seq;
        seq[pos] = nums[i];
        id[pos] = i;
        pre[i] = pos > 0 ? id[pos - 1] : -1;
        if (pos == L - 1) lastIdx = i;
        if (pos == L) ++L;
    }
}

void Print(int idx)
{
    if (idx == -1) return;
    Print(pre[idx]);
    cout << nums[idx] << '\n';
}

void solve()
{
    cout << L << "\n-\n";
    Print(lastIdx);
}

int main()
{
    LIS();
    solve();
}

參考資料

UVA 481: What goes up - Algorithm challenge