赛后补题——gk的爬山之旅

我们可以发现，每一步的最优解就是选择这座山右边第一高的或者左边第一高的，所以很明显，要用单调栈来进行一个维护。

//还差一个条件的实现，就是从右开始向后扫，找最右边第一个比堆顶大时
//碰见重复的连续串，应该选择第一个；找左边的则是找最后一个
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e6+7;
int g[M],h[M],l[M],r[M];
int f[M];
int t,n;
stack<int> q;
int jud(int a, int b){
    if(h[a]>h[b])
        return b;
    if(h[a]==h[b])
        return a;
    if(h[a]<h[b])
        return a;
    return 0;
}
int send(int x){
    if(f[x]!=0)
        return f[x];
    if(l[x]!=0) f[x] = max(f[x], send(l[x]) + abs(g[l[x]] - g[x]));
    if(r[x]!=n+1) f[x] = max(f[x], send(r[x]) + abs(g[r[x]] - g[x]));
    return f[x];//记忆化搜索（之前一直不会写，重点体会一下）
}
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        
        for(int i=1; i<=n; i++)
            cin>>h[i];
        for(int i=1; i<=n; i++)
            cin>>g[i];
        
        h[0]=1e9+1,h[n+1]=0;
        q.push(n+1);
        for(int i=n; i>=0; i--){
            while(!q.empty()&&h[i]>h[q.top()]){
                l[q.top()]=i;
                q.pop();
            }
            q.push(i);
        }
        while(!q.empty())
            q.pop();//找每个的左边第一大
        
        h[0]=0,h[n+1]=1e9+1;
        q.push(0);
        for(int i=1; i<=n+1; i++){
            while(!q.empty()&&h[i]>h[q.top()]){//注意要把判断不为空的条件放前面
                r[q.top()]=i;
                q.pop();
            }
            //cout<<i<<" ";
            q.push(i);
        }
        while(!q.empty())
            q.pop();//找每个的右边第一大

        h[n+1]=1e9+1;
        for(int i=1; i<=n; i++){
            ll sum=0;
            int hj=i;
            sum=send(hj);
            cout<<sum<<" ";
        }
    }
    return 0;
}