BZOJ

分析

比较简单的DP。

考虑把M拆成两个^去做。

设$f[i]$表示$1$~$i$变为上升的最小代价，$g[i]$表示$i$~$n$变为递减的最小代价。

这个很容易DP出来。

然后，设$l[i]$表示以$i$为中点，左边构成^的最小代价，$r[i]$表示以$i$为中点，右边构成^的最小代价。

这个似乎也很容易搞出来。

最后答案为$\min\left\{l[i]+r[i]\right\}$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=100000+10;

int a[MAXN],f[MAXN],g[MAXN];
int l[MAXN],r[MAXN];

mainint main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    a[0]=-1;
    for (re int i=1;i<=n;++i) f[i]=f[i-1]+max(a[i-1]-a[i]+1,0ll);
    for (re int i=n;i>=1;--i) g[i]=g[i+1]+max(a[i+1]-a[i]+1,0ll);
    for (re int i=3,j=2;i<=n-2;++i) {
        while (j<i-1&&max(f[j+1],g[j+1]-g[i])<=max(f[j],g[j]-g[i])) ++j;
        l[i]=max(f[j],g[j]-g[i]);
    }
    for (re int i=n-2,j=n-1;i>=3;--i) {
        while (j>i+1&&max(g[j-1],f[j-1]-f[i])<=max(g[j],f[j]-f[i])) --j;
        r[i]=max(g[j],f[j]-f[i]);
    }
    int ans=1e16;
    for (re int i=3;i<=n-2;++i) ans=min(ans,l[i]+r[i]);
    printf("%lld\n",ans);
    return 0;
}