题意
给定 \(N\times M\) 的网格,给定 \(K\) 个二元组 \((x_1, y_1), (x_2, y_2), \cdots , (x_K, y_K)\),求从 \((1, 1)\) 到 \((N, M)\) 只向右或向下走最多可以经过多少个给定的方格,并给出一种方案。
赛时 不会
赛后
由于只能向右或向下走,因此当前所处位置 \((nowx, nowy)\) 中,\(nowx\) 和 \(nowy\) 一定都是不降的。因此,我们可以将所有给定的点按照 \(x\) 为第一关键字,\(y\) 为第二关键字升序排序(事实上,这就是 pair 的排序方法),这样,问题就转化为了 \(O(n \log n)\) 的时间复杂度求所有点的 \(y\) 的最长不降子序列(LIS)及其中一种方案。
LIS
我们记录一个单调栈,当遍历到 \(y_i\) 时,在栈中查找第一个 \(>y_i\) 的元素并用 \(y_i\) 将其替换,特别的,如果没有这样的元素,则将 \(y_i\) 压入栈中,结合二分可以做到 \(O(n \log n)\),但是这样,单调栈中记录的元素并不是可行的方案。因此,需要记录 \(y_i\) 被放入栈中时的位置 \(pos_i\),这样,只需要倒序枚举,且使得最终答案满足 \(LIS_i\) 上的元素的 \(pos\) 为 \(i\) 即可。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 200005;
PII points[N], p[N];
int n, m, k;
int stk[N], top = 0, po[N], len;
int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i ++ ) scanf("%d%d", &points[i].x, &points[i].y);
sort(points + 1, points + k + 1);
for (int i = 1; i <= k; i ++ ){
int pos = upper_bound(stk + 1, stk + top + 1, points[i].y) - stk;
top = max(top, pos);
stk[pos] = points[i].y;
po[i] = pos;
}
printf("%d\n", top);
len = top;
for (int i = k; i; i -- ){
if (!len) break;
if (po[i] == len) stk[len -- ] = points[i].y;
}
for (int i = 1, j = 1; i <= top; j ++ )
if (points[j].y == stk[i]) i ++ , p[i] = points[j];
p[1] = {1, 1}, p[top + 2] = {n, m};
for (int i = 2; i <= top + 2; i ++ ){
for (int j = 1; j <= p[i].x - p[i - 1].x; j ++ ) printf("D");
for (int j = 1; j <= p[i].y - p[i - 1].y; j ++ ) printf("R");
}
return 0;
}
标签:Coins,int,Gather,abc369,给定,LIS,元素,include
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/luoguAT_abc369_f