MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

题解 P3971 【[TJOI2014]Alice and Bob】

posted on 2019-10-22 10:42:26 | under 题解 |

原序列为$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$数组统计答案就可以了

#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;
}