题解 P6489 【[COCI2010-2011#6] USPON】

· · 题解

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;//结束，拉闸拉闸拉闸 
}

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

谢谢大佬们赏脸~