🐱 猫咪运动

0题目在说什么

• N 座塔排成一列，高度恰好是 1..N 的一个排列（互不相同）。
• 🐱 一开始站在最高的那座塔（高度 N）上。
• 高桥君可以按任意顺序撤掉还立着的塔。
• 如果撤掉的正好是猫脚下的那座塔，猫必须跳到「当前可达的最高的塔」上，跳跃距离累加进总分。
• 求总分的最大值。

下面这个例子用的数组是 P = [3,1,6,4,7,2,5]（位置 1..7），最高塔在位置 5，高度 7。

1三个关键观察

观察 ①：猫永远站在「它所在连通块」的最高塔上

猫起点是全局最高塔。之后它每次只跳向「可达的最高塔」。 拆掉别的塔并不会让猫移动（猫只在自己脚下塔被拆时才跳）， 所以猫站的那座塔，在它所在的连续存活段里永远是最高的。

观察 ②：脚下的塔被拆 → 连通块裂成左右两段

设猫在位置 u。把 u 拆掉后，它所在的连续段断成左右两段。 猫必须跳到「左段最高塔」和「右段最高塔」中更高的那一个， 跳跃距离 = |目标位置 - u|。

观察 ③：不想要的那一段，可以提前白送掉

关键在这里 👉 假设我们想逼猫往左走。 那就在拆掉 u 之前，把右段的所有塔统统拆光。 拆的时候猫在 u 上，不在那些塔上，所以完全不产生任何距离。 等右段空了，再拆 u，猫就只剩左段可去。

所以「撤塔顺序」这个看似庞大的搜索空间，被压缩成了：在猫的每一步，选左 or 选右。

把「区间最高塔」递归下去 → 笛卡尔树

这样长出来的树，就叫 大根笛卡尔树。 于是：猫的整条轨迹，就是从根出发，每次选左孩子或右孩子往下走的一条路径。

DP 就出来了

设 f(u) 表示：猫站在节点 u 的塔上（u 的整棵子树都还立着），到运动结束还能获得的最大总距离。

叶子节点 f = 0。答案就是 f(根)。

2递归建树动画：一层层找「区间最高塔」

上面是塔阵（黄色 = 当前区间最高塔，亮蓝 = 当前区间），下面是长出来的树。点「下一步」看递归过程。

3O(N) 建树：单调栈

递归找最大值是 O(N²)。用单调栈可以一遍扫完：

• 从左到右扫位置 i，维护一个高度递减的栈。
• 不断弹出栈顶那些比 P[i] 矮的塔；最后弹出来的那个就是 lc[i]（因为它是被 i 吞掉的、最靠右的那棵子树的根）。
• 弹完之后如果栈非空，栈顶就成了 rc[栈顶] = i（i 顶替了它原来的右孩子）。
• 把 i 压入栈。

扫描结束后，栈底元素就是整棵树的根。

4树形 DP：按值从小到大算 f

因为父节点的值一定大于子节点的值（笛卡尔树是大根堆！）， 所以只要按高度 1 → N 的顺序处理节点，就天然是一个合法的后序（孩子先算完）。

5代码

// ABC435F 猫咪运动
// 大根笛卡尔树 + 树形 DP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> P(N + 1), pos(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> P[i];
        pos[P[i]] = i;
    }
    // 单调栈建大根笛卡尔树 (按位置顺序, 值大者为父)
    vector<int> lc(N + 1, 0), rc(N + 1, 0), st;
    for (int i = 1; i <= N; ++i) {
        int last = 0;
        while (!st.empty() && P[st.back()] < P[i]) {
            last = st.back();
            st.pop_back();
        }
        if (!st.empty()) rc[st.back()] = i;
        lc[i] = last;
        st.push_back(i);
    }
    int root = st[0];
    vector<ll> f(N + 1, 0);
    for (int v = 1; v <= N; ++v) {   // 值升序 = 后序
        int u = pos[v];
        ll best = 0;
        if (lc[u]) best = max(best, (ll)abs(lc[u] - u) + f[lc[u]]);
        if (rc[u]) best = max(best, (ll)abs(rc[u] - u) + f[rc[u]]);
        f[u] = best;
    }
    cout << f[root] << '\n';
    return 0;
}