题解 | gk的爬山之旅

单调栈一般就是栈内的更新细节...无数次折磨了

首先发现这个图是个dag(有向无环图),假如对值比它大的最近的左右两个点连边的话,然后对dag做个简单的线性dp就好了.

细节就是一段相同的时候,因为数据保证递增,在前面的时候肯定选取最前面的最优,在后面的时候肯定选最后面最优,然后一定要在栈内更新,比如3 3 2 1 3 3你在栈外更新肯定是错的,也可能是我调k脑抽了.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int mod=1e9+7;

//对于每个点 连接左右两点中比较小的一个点 肯定是无环的. 
ll f[N];
int h[N],g[N],l[N],r[N],L[N],R[N];
int pre[N],suf[N];//前缀的最小值,后缀的最大值在哪个位子 
bool vis[N];
vector<int>G[N];

void dfs(int u)
{
    if(f[u]!=-1)    return;
    f[u]=0;
	for(int v:G[u])
	{
        if(f[v]==-1)    dfs(v);
		f[u]=max(f[u],f[v]+abs(g[u]-g[v]));
	}
}

void run()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)	f[i]=-1,G[i].clear(),l[i]=r[i]=-1,L[i]=R[i]=i;
    h[n+1]=0;h[0]=0;
    for(int i=1;i<=n;i++)
    	scanf("%d",&h[i]);
    for(int i=1;i<=n;i++)
    	scanf("%d",&g[i]);
    stack<int>s;
    for(int i=1;i<=n;i++)//栈尾到栈顶单调递减. 
    {
    	while(s.size()&&h[s.top()]<=h[i])	
        {
            if(h[s.top()]==h[i])    L[i]=s.top();
            s.pop();
        }
        if(s.size())	l[i]=L[s.top()];
    	s.push(i);
	}
    while(s.size())	s.pop();
    for(int i=n;i>=1;i--)//栈尾到栈顶单调递减. 
    {
    	while(s.size()&&h[s.top()]<=h[i])	
        {
            if(h[i]==h[s.top()])    R[i]=s.top();
            s.pop();
        }
        if(s.size())	r[i]=R[s.top()];
    	s.push(i);
	}
    while(s.size())	s.pop();
    for(int i=1;i<=n;i++)
    {
    	if(l[i]==-1&&r[i]==-1)	continue;
		else if(l[i]==-1)		G[i].push_back(r[i]);
		else if(r[i]==-1)		G[i].push_back(l[i]);
		else
		{
            G[i].push_back(r[i]);G[i].push_back(l[i]);
		}
	}
    for(int i=1;i<=n;i++)
    {
    	if(!vis[i])	dfs(i);
	}
	for(int i=1;i<=n;i++)
		printf("%lld ",f[i]);
	puts("");
}

int main()
{
	int T=1;
	cin>>T;
	while(T--)
	{
		run();
	}
	return 0;
}