【PNR#2 Div1 B】排序(线段树)(DP)
排序
题目链接:PNR#2 Div1 B
题目大意
给你一个排列,有一个一开始为空的栈,按顺序处理排列的每个数,如果栈是空的或者比栈顶大就放入栈中,否则可以选择什么都不做或者把栈顶元素弹出并放入这个数,要求全程栈中元素从底到顶严格上升。
要你求最后栈大小的最大值。
思路
考虑一个 DP 设 f i f_{i} fi 为当前子序列结尾是 a i a_i ai 而且会最后会有 a i a_i ai 的最大答案。
那你就考虑
f
i
+
1
→
f
j
f_i+1\rightarrow f_j
fi+1→fj,那如果我们找到第一个大于
a
i
a_i
ai 的位置
n
x
t
i
nxt_i
nxti,那就是
n
x
t
i
∼
n
x
t
n
x
t
i
−
1
nxt_i\sim nxt_{nxt_i}-1
nxti∼nxtnxti−1,而且要里面的
a
j
>
a
i
a_j>a_i
aj>ai。
那前面条件看着很友好,于是考虑处理掉后面的,就按
a
a
a 值从小到大来 DP,前面的条件用线段树来搞即可。
代码
#include<set>
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 5e5 + 100;
int n, a[N], pl[N], nxt[N], sta[N], f[N];
struct XD_tree {
int val[N << 2];
void up(int now) {
val[now] = max(val[now << 1], val[now << 1 | 1]);
}
int query(int now, int l, int r, int L, int R) {
if (L <= l && r <= R) return val[now];
int mid = (l + r) >> 1, re = 0;
if (L <= mid) re = max(re, query(now << 1, l, mid, L, R));
if (mid < R) re = max(re, query(now << 1 | 1, mid + 1, r, L, R));
return re;
}
void change(int now, int l, int r, int pl, int va) {
if (l == r) {
val[now] = va; return ;
}
int mid = (l + r) >> 1;
if (pl <= mid) change(now << 1, l, mid, pl, va);
else change(now << 1 | 1, mid + 1, r, pl, va);
up(now);
}
}T;
int main() {
// freopen("ex_sort5.in", "r", stdin);
// freopen("write.txt", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), pl[a[i]] = i;
for (int i = n; i >= 1; i--) {
while (sta[0] && a[sta[sta[0]]] < a[i]) sta[0]--;
if (!sta[0]) nxt[i] = n + 1;
else nxt[i] = sta[sta[0]];
sta[++sta[0]] = i;
}
nxt[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
f[i] = T.query(1, 1, n, nxt[pl[i]], nxt[nxt[pl[i]]] - 1) + 1;
T.change(1, 1, n, pl[i], f[i]);
}
printf("%d", T.query(1, 1, n, 1, nxt[1] - 1));
return 0;
}
相关文章
- 【华为OD机试真题 python】数组去重和排序 【2022 Q4 | 100分】
- 并发集合(四)用优先级对使用阻塞线程安全的列表排序
- ps - 按进程消耗内存多少排序
- 排序算法--计数排序(CountSort)的原理、排序过程、注意点及代码示例
- 【剑指offer|5.在排序数组中查找数字I】
- MySQL也有潜规则 – Select 语句不加 Order By 如何排序?
- 字符串数组排序的快速排序实现
- nyoj 4 ASCII码排序
- mysql 按照权重排序
- 巩固复习(对以前的随笔总结)_排序
- 前端排序算法 - 选择排序算法 (4)
- 【bzoj1093】[ZJOI2007]最大半连通子图 Tarjan+拓扑排序+dp