【题解】【上海】【平整序列】

做一次操作将区间[i,j]加x(1或-1)等价于将b[i-1]+x、b[j+1]-x，最后要使得a[1]~a[n]均为0等价于差分数组b全为0。
故题意等价于：从b[1]~b[n+1]挑选b[i]、b[j]，让b[i]+x、b[j]-x，最少操作多少次可以使得数组b全为0。而对于差分数组b中正整数b[k]，要将其变为0，最少需要操作b[k]次，因此总操作次数一定不少于差分数组中所有正整数b[k]之和！
因而，只需要将构造出的查分数组正整数累加至答案即可。注意：差分数组区间[0,n+1]。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
long long a[N],b[N],ans;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    b[n+1]=a[n+1]-a[n];
    for(int i=1;i<=n+1;i++){
        if(b[i]>0)ans+=b[i];
    }
    cout<<ans;
    return 0;
}