飛黃騰達 題解｜APCS 2021 年 1 月高級 第 4 題

前置知識

這題是「最長遞增子序列」換個包裝，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 排序 pair：sort 一個 vector<pair<int,int>> 時先比第一個值、相同再比第二個值；NTUCPC Guide〈排序演算法〉。
• DP 的狀態與轉移：NTUCPC Guide〈狀態與轉移〉——本題的狀態是「以第 \(i\) 顆果實結尾」。

簡潔題意

從 \((0, 0)\) 出發，每一步可以移到 \(x\)、\(y\) 都不小於目前位置的任何一個點。平面上有 \(n\) 顆果實（座標互異），走到它的位置就能吃掉。求最多能吃幾顆（\(1 \le n \le 2 \times 10^5\)，\(1 \le x_i, y_i \le 10^7\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(20\) 分）：\(n \le 100\)，\(x_i, y_i \le 100\)。
• 子題組 2（\(30\) 分）：\(n \le 1000\)。
• 子題組 3（\(50\) 分）：無額外限制。

一步可以跳到任何右上方（含正右、正上）的點，所以「能不能依序吃到 \(f_1, f_2, \ldots\)」只看一件事：每一顆的 \(x\)、\(y\) 都不小於前一顆。

先拿下 20 分：座標只到 100，整張格子做 DP

座標都在 \(100 \times 100\) 的格子裡，直接定義 \(f[x][y]\) ＝ 走到 \((x, y)\) 時最多吃了幾顆。走到 \((x, y)\) 的前一步在它的左邊或下面（跳遠一點的走法，拆成一格一格走也到得了），所以

答案是 \(f[100][100]\)。

#include <bits/stdc++.h>
using namespace std;

int f[101][101];     // 一開始全是 0；有果實的格子先標成 1

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        f[x][y] = 1;                       // 子題組 1 保證 x, y <= 100
    }
    for (int x = 1; x <= 100; x++)
        for (int y = 1; y <= 100; y++)
            f[x][y] += max(f[x - 1][y], f[x][y - 1]);   // 從左邊或下面走過來
    cout << f[100][100] << '\n';
    return 0;
}

格子 \(10^4\) 個、每格 \(O(1)\)。座標超過 \(100\) 的測資這份程式會寫到陣列外面——這是正常的，子題組 1 的 \(20\) 分穩穩到手。

從 20 分到 50 分：排序之後只剩一個條件

座標到 \(10^7\) 就不能開格子了，改成只看果實。先把果實依 \(x\) 由小到大排序，\(x\) 相同再依 \(y\) 由小到大（sort 一個 pair 的 vector 就是這個順序）。排好之後，排在前面的 \(x\) 一定不比後面大，「能不能接著吃」就只剩 \(y\) 一個條件：

\(dp[i]\) ＝ 最後一顆吃第 \(i\) 顆（排序後的編號）時，最多吃幾顆。 \(dp[i] = 1 + \max\{\,dp[j] : j < i,\ y_j \le y_i\,\}\)，沒有這種 \(j\) 就是 \(1\)。

同一個 \(x\) 的果實為什麼要依 \(y\) 排？因為它們可以由下往上全部吃到，排成 \(y\) 遞增才會被當成「可以接著吃」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> fruit(n);       // (x, y)
    for (auto &f : fruit) cin >> f.first >> f.second;
    sort(fruit.begin(), fruit.end());      // x 小的在前，x 相同則 y 小的在前

    vector<int> dp(n, 1);                  // 至少吃它自己這一顆
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (fruit[j].second <= fruit[i].second)   // y 不下降就能接著吃
                dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
    return 0;
}

這就是最長不下降子序列：排序後的 \(y\) 序列裡，挑出最長的「不會變小」的子序列。\(O(n^2)\) 在 \(n = 1000\) 時瞬間完成，\(n = 2 \times 10^5\) 時本站實測超過時限——子題組 3 要換個算法。

從 50 分到 100 分：同樣長度的鏈，只記結尾最小的

\(O(n^2)\) 慢在「每顆果實都回頭掃一遍前面所有的 \(dp\)」。換個角度記：

\(tail[c]\) ＝ 目前為止，長度為 \(c + 1\) 的鏈之中，結尾 \(y\) 最小可以是多少。

結尾越小，後面越容易接得上，所以同長度只留結尾最小的那條就夠。這個陣列是遞增的（長度多一的鏈，去掉最後一顆就是一條短一點的鏈，結尾更小）。新的一顆 \(y\) 來了：

1. 它能接在所有「結尾 \(\le y\)」的鏈後面，最長的那條長度就是「第一個比 \(y\) 大的 tail 的位置」——用 upper_bound 二分搜。
2. 接上去之後得到一條長度多一的鏈，結尾是 \(y\)：若那個位置超出陣列就 push_back（鏈變長了），否則把那格換成 \(y\)（同長度、結尾更小）。

為什麼是 upper_bound 不是 lower_bound：相等的 \(y\) 也能接在後面（正右方可以走），所以要找「第一個嚴格大於 \(y\)」的格子。圖 1 用七顆果實走一遍。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> fruit(n);
    for (auto &f : fruit) cin >> f.first >> f.second;
    sort(fruit.begin(), fruit.end());

    vector<int> tail;                      // tail[c]：長度 c+1 的鏈，結尾 y 最小是多少
    for (auto [x, y] : fruit) {
        auto it = upper_bound(tail.begin(), tail.end(), y);   // 第一個比 y 大的格子
        if (it == tail.end()) tail.push_back(y);              // 接出更長的鏈
        else *it = y;                                         // 同長度，結尾換成更小的
    }
    cout << tail.size() << '\n';
    return 0;
}

排序 \(O(n \log n)\)、每顆果實一次二分搜 \(O(\log n)\)，\(n = 2 \times 10^5\) 本站實測不到 \(0.1\) 秒。要注意 tail 存的是「結尾最小值」，不是真正的一條鏈——它的長度才是答案。

測過再交：範例只有三顆、沒有同一排的果實

範例三顆果實的 \(x\)、\(y\) 都互異。沒蓋到的：同一個 \(x\) 上好幾顆、同一個 \(y\) 上好幾顆（走正右方）、一顆都接不上的局面、座標頂到 \(10^7\)。

六筆都親眼看過正確，這題就穩了。