[題解] TIOJ 2195 粉刷護欄 (TOI 2021 初選 pC)

題意

上下有個有一根木樑
然後中間有 n 條可能會相交的木板
找出最多可以釘上幾條木板並構造最大字典序的解
(細節自己去 TIOJ 看 :<)

前言的部分

因為這題看起來沒人寫題解
於是我就發了這篇文章 ouob

轉化問題

仔細觀察問題
我們可以把問題轉換成 LIS 或 LCS

LCS 的話應該不難理解
因為要釘最多木板其實就是要在上下兩條陣列各選一個共同的子序列
然後把每個數字一一對應釘起來
但是 LCS 需要 $O(n^2)$ 的時間複雜度才能計算
所以一定會 TLE

接著是 LIS 的作法
仔細觀察題目的話可以發現
如果木板有"座標"的話
其實我們在做的事情就是"對木板做 LIS"
更精確一點的說
就是我們其實可以把木板在上樑的點跟下樑的點綁成一個 pair 做 LIS
我們說木板 A 的座標小於木板 B 代表 A 的下樑座標跟上樑座標都小於 B

至於座標的部分大概就是這個意思：
以附圖為例
木板 3 的座標就是 (2, 1)
木板 4 的座標就是 (5, 3)
木板 5 的座標就是 (4, 4)

如何構造解

如果用最普通的 DP 方式
就算能構造解也很難求最大字典序
於是我們修改一下計算方式
把轉移式改成 “定義 $dp[i]$ 為把第 $i$ 個元當頭素能構造出的 LIS”
其實就只是倒著做 LIS 然後 Increasing 改成 Decreasing 就好了

做完 DP 之後
我們要從 dp 值大的開始構造
先找一個 dp 值跟最終 LIS 一樣長而且字典序最大的元素
接著往右找小一點的直到 1 為止

實作細節

關於上面提到的"座標"
實際上不需要真的把座標算出來
我們只需要把第二個陣列(代表下梁座標的陣列)每一個元素替換成該元素在第一個陣列出現的位置
並對第二個陣列做 LIS 就可以了
原因的話講起來有點麻煩 自己想吧

一個小測資

第一次傳 WA 了一片
然後 debug 的時後測出這樣的測資會出錯
如果你也找不到你的程式坐在哪裡的話
不仿測試看看這筆測資

3
3 1 2
1 2 3

最後的程式碼

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MAXN = 2e5 + 10;

// map 會超時，所以改 unordered_map
unordered_map<int, int> rpos;
unordered_map<int, int> pos;
vector<int> lens[MAXN];
int v[MAXN];

bool cmp(int a, int b) {
    return rpos[v[a]] > rpos[v[b]];
}

signed main() {
    io;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        // 紀錄元素座標
        pos[tmp] = i;
    }
    for (int i = 1; i <= n; i++) {
        int tmp;
        cin >> tmp;
        // 將陣列的值設定為目前元素在上面陣列的出現位置
        v[i] = pos[tmp];
        // 把坐標在映射回他的值，輸出的時候會用到
        rpos[pos[tmp]] = tmp;
    }
    // LIS 的部分
    // 作法類似：https://usaco.guide/gold/lis?lang=cpp
    int len = 0;
    vector<int> dp;
    for (int i = n; i >= 1; i--) {
        int ans = 0; // 儲存目前 dp 值：以 i 為開頭能構造出多長的 LIS
        if (dp.empty() || dp.back() > v[i]) {
            dp.push_back(v[i]);
            // 紀錄目前的 dp 值
            ans = dp.size();
        } else {
            auto ite = upper_bound(all(dp), v[i], greater<int>());
            *ite = v[i];
            // 紀錄目前的 dp 值
            ans = ite - dp.begin() + 1;
        }
        // len 維護最終 LIS 長度
        len = max(len, ans);
        // 紀錄每個長度的解
        lens[ans].push_back(i);
    }
    // 構造解
    int cur = 0;
    for (int i = len; i >= 1; i--) {
        // 依照字典序做 sort
        sort(all(lens[i]), cmp);
        for (auto j : lens[i]) {
            // 排除在目前選到的元素左邊的元素
            if (j <= cur) continue;
            // 排除加入後會相交的元素 (用於排除文章中寫的“一個小測資”那段的 Case)
            if (v[j] < v[cur]) continue;
            cur = j;
            // 把 index 映射回去並輸出
            cout << rpos[v[j]] << " ";
            break;
        }
    }
}