题解 P3971 【[TJOI2014]Alice and Bob】
MorsLin
·
·
题解
原序列为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一定是满足上述所有条件的
最后对$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;
}
```