题解：P11876 收徒！

· · 题解

题目大意

给定一个 H\times W 的空白方格，从中选出 n 个点附上 1 的价值。问从 (1,1) 走到 (H,W) 只能向下和向右前行，所能获得的最大价值，并输出路径。

解题思路

部分分思路

很容易想到坐标动态规划，然后用数组记录每次决策的转移方向。但是 H 和 W 很大不能开这么大的数组，否则会炸空间。 代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int h, w, n, x, y;
int dp[N][N], mp[N][N];
char pre[N][N];
void dfs(int x, int y) {
    if (x == 1 && y == 1) return ;
    if (pre[x][y] == 'D')   dfs(x - 1, y);
    else    dfs(x, y - 1);
    cout << pre[x][y];
}
int main() {
    cin >> h >> w >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        mp[x][y] = 1;
    }
    for (int i = 2; i <= n; i++)
        dp[i][1] = dp[i - 1][1] + mp[i][1], pre[i][1] = 'D';
    for (int j = 2; j <= w; j++)
        dp[1][j] = dp[1][j - 1] + mp[1][j], pre[1][j] = 'R';
    for (int i = 2; i <= h; i++)
        for (int j = 2; j <= w; j++) {
            if (dp[i - 1][j] > dp[i][j - 1]) {
                pre[i][j] = 'D';
                dp[i][j] = dp[i - 1][j] + mp[i][j];
            } else {
                pre[i][j] = 'R';
                dp[i][j] = dp[i][j - 1] + mp[i][j];
            }
        }
    cout << dp[h][w] << endl;
    dfs(h, w);
    return 0;
}

满分思路

考虑到数据范围很大，显然不能直接坐标动态规划。由于只能向下向右并且价值为 1。 可以考虑把问题转换为最长不下降子序列问题，用效率为 O(n\log{n}) 的贪心和二分方法计算答案。即从 n 个按 x 坐标从小到大排序的点中找到一条最长的一条链。答案可以直接构造。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int h, w, n, c[N], dp[N], nowx[N], nowy[N], k;
int pre[N];     //记录第i个数的前一项的下标
int lst[N];     //记录长度为len的最后一项的下标
string ans;
struct node {
    int x, y;
    bool operator<(node &b) {
        if (x == b.x) return y < b.y;
        return x < b.x;
    }
} a[N];
void dfs(int now) {
    if (now == 0) return;
    dfs(pre[now]);
    ++k;
    nowx[k] = a[now].x, nowy[k] = a[now].y;
}
int 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);
    dp[1] = a[1].y;
    lst[1] = 1, pre[1] = 0;
    int len = 1;
    for (int i = 2; i <= n; i++) {
        if (dp[len] <= a[i].y) {        //如果这一项能接在最长的一项后面
            pre[i] = lst[len];          //当前项的前驱为之前长度为len的最小的最长项
            dp[++len] = a[i].y;         //记录当前长度为len的子序列的最后一项
            lst[len] = i;               //记录当前长度为len的最后一项的下标
        } else {
            int x = upper_bound(dp + 1, dp + 1 + len, a[i].y) - dp; //查找等于len的
            pre[i] = lst[x - 1];
            dp[x] = a[i].y;
            lst[x] = i;
        }
    }
    cout << len << endl;
    nowx[1] = nowy[1] = k = 1;
    dfs(lst[len]);                      //递归记录路径
    ++k, nowx[k] = h, nowy[k] = w;
    for (int i = 2; i <= k; i++) {      //根据曼哈顿距离构造答案
        string D(nowx[i] - nowx[i - 1], 'D');
        string R(nowy[i] - nowy[i - 1], 'R');
        ans += D + R;
//      cout << nowx[i] << " " << nowy[i] << endl;
    }
    cout << ans;
    return 0;
}