单调队列贪心

简单证明: 如果有这样的四个数 a,b,c,d(a < b , b > c , d < c)

d - a = (d-c) + (c-a) < (d-c) + (b-a)

有如下代码

#include <iostream>
using namespace std;
const int N = 1E5+10;
int a[N];
int dp[N];
int q[N];
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)   cin  >> a[i];
    int hh,tt;
    hh = tt = 0;
    q[0] = 1;
    int ans = 0;
    for(int i=2;i<=n;i++){
        while(hh<=tt && a[q[tt]] >= a[i]){
            ans += a[q[tt]] - a[q[hh]];
            tt = -1,hh = 0;
        }
        q[++tt] = i;
        if(i == n) ans += a[q[tt]] - a[q[hh]];

    }
    cout << ans;
}