自动搬运

查看原文

来自洛谷，原作者为

	王炸拆开打 AFO[++head]="王炸拆开打"

搬运于2025-08-24 22:21:17，当前版本为作者最后更新于2020-09-15 21:24:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

3分钟出思路，10分钟出代码（大佬发言）

乍一看：上升子序列问题

但是注意题中的要求，需要连续的高度严格递增的山路

所以我们的递推只需要$O(n)$,只用根据i-1的状态来决定i的状态

计算目前落差公式：$h[i]=a[i]-a[j]+h[j]$

(a[i]点的高度, h[i]子序列目前落差)

放代码

#include<iostream>
using namespace std;
int n,a[100001],f[10001],h[10001];//a[i]—点的高度、f[i]上升子序列长度、h[i]子序列目前落差 
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]);f[i]=1;}//f[i]数组的初始化，每个数自己都是一个长度为一的上升序列 
   	for(int i=2;i<=n;i++){
   		int j=i-1;//j来代替i-1，更加简洁 
		if(a[j]<a[i]){//i大于前一个 
			f[i]=f[j]+1;//则以i为结尾的上升子序列长度加一 
			h[i]=a[i]-a[j]+h[j];//落差加一 
		}
    }
    int maxx=-1;
    for(int i=1;i<=n;i++) maxx=max(maxx,h[i]);//求最大落差 
    printf("%d",maxx);
    return 0;//结束，拉闸拉闸拉闸 
}

发现和第一篇题解相似，但完全是自己想的（勿喷）

谢谢大佬们赏脸~