Statement

给定一个 H×WH \times W 的网格以及 NN 个硬币的位置，从 (1,1)(1, 1) 开始每次往下或往右移动一个单元格，求到达 (H,W)(H, W) 单元格能拾取的最多硬币以及该路径。

Solution

考虑如何转化问题：由于每次只能向下或者向右走，则运动路径在二维平面上看来必然是在横纵坐标上分别非严格单调递增的。换句话说，第 ii 个硬币可以被捡到当且仅当上一个捡到的硬币 jj 满足 Xj≤XiX_j \le X_i 且 Yj≤YiY_j \le Y_i，很显然的二维偏序求最长上升子序列问题。

题目中的 H,W≤2×105H,W \le 2 \times 10^5，朴素的 O(n2)O(n^2) 求法无法通过，我们采取更为优秀的二分查找法，定义 fif_i 表示满足长度为 ii 的非严格上升子序列的末尾的最小值，遍历序列时找到 ff 数组中最后一个小于等于当前数的下一个数（即大于待选数的第一个数），将这个数替换进去（因为它满足可以构成长度为 ii 的子序列并且值更优）。

这里用到了一种贪心的思想，末尾的数更小显然可以匹配更多的数。

这种做法不可以直接求出路径方案，就像最短路一样，它的 ff 数组在不断的变化，它代表的不是点的下标而是值的大小，类似最短路路径方案的求法，我们记录每一个更新进来的数的下标以及它的前驱，不断的回退前驱就可以得出路径方案了。

具体的做法见代码

Code

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
signed main()
{
    cin >> h >> w >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + 1 + n);

    for (int i = 1; i <= n; i ++)
    {
        if (q[len] <= a[i].y)
        {
            q[++ len] = a[i].y, id[len] = i, pre[i] = len >= 2 ? id[len - 1] : -1;
            continue;
        }

        int l = 1, r = len, res = 0;
        while (l <= r)
        {
            int mid = l + r >> 1;
            if (q[mid] > a[i].y) r = mid - 1, res = mid;
            else l = mid + 1;  
        }
        q[res] = a[i].y, id[res] = i, pre[i] = res >= 2 ? id[res - 1] : -1;    // 第一个数不存在前驱
    }
    cout << len << '\n';

    int cur = id[len], idx = len;
    while (~cur)    // 不断寻找前驱直到 cur ==
    {
        path[idx --] = cur;
        cur = pre[cur];
    }

    path[0] = 0, path[++ len] = n + 1, a[0] = {1, 1}, a[n + 1] = {h, w};    // 定义边界范围
    for (int j = 1; j <= len; j ++)
    {
        int tempx = a[path[j]].x - a[path[j - 1]].x, tempy = a[path[j]].y - a[path[j - 1]].y;
        while (tempx --) putchar('D');
        while (tempy --) putchar('R');
    }

    return 0;
}