题解 P3971 【[TJOI2014]Alice and Bob】
MorsLin
2019-10-22 10:42:26
原序列为$x$，输入的序列为$a$。
因为题目中是**上升子序列**和**下降子序列**，所以原序列中相同的元素没有贡献，因此不妨设$x$为$1$~$n$的一个排列
$a_i$是以$x_i$为结尾的最长上升子序列的长度，所以对于所有的$a_k = a_i - 1$，一定存在至少一个$k$使$x_k < x_i$
如果要使Bob得分尽量高，可以贪心的使$a_i$较大的$x_i$尽量小，$a_i$相同的使$i$较大的$x_i$（即相对靠后的元素）尽量小
考虑如何构造出符合上述条件的$x$
对于$i$，我们可以向离它最近的满足$a_k = a_i-1$的$k$连一条边，这样可以构造出一棵树（以$0$为根）
我们直接对这棵树求出它的dfs序数组$dfn$，则$dfn$就是一个满足上述条件的序列
因为前向星有一个特殊的性质：晚连上的边会被先遍历到。同时因为dfs先序遍历的特性（节点的dfs序小于它的子树中任意点的dfs序），求出来的$dfn$一定是满足上述所有条件的
$0$是虚根，可以方便我们遍历，不过它会使$x_i$全都加$1$，但这样显然不会对答案造成影响
最后对$dfn$数组统计答案就可以了
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
struct zzz {
int t, nex;
}e[100010 << 1]; int head[100010], tot;
inline void add(int x, int y) {
e[++tot].t = y;
e[tot].nex = head[x];
head[x] = tot;
}
int a[100010], b[100010], dfn[100010], cnt, num;
void dfs(int x, int fa) {
dfn[x] = ++cnt;
for(int i = head[x]; i; i = e[i].nex) {
if(e[i].t == fa) continue;
dfs(e[i].t, x);
}
}
int main() {
int n = read();
for(int i = 1; i <= n; ++i) {
int x = read();
add(a[x-1], i); add(i, a[x-1]); a[x] = i;
}
dfs(0, 0); LL ans = 0;
for(int i = n; i >= 1; --i) {
int pos = 0;
if(dfn[i] > b[num]) b[++num] = dfn[i], pos = num;
else pos = upper_bound(b+1, b+num+1, dfn[i]) - b;
b[pos] = min(b[pos], dfn[i]);
ans += (LL)pos;
}
cout << ans << endl;
return 0;
}
```