题意

经典题。给出序列 ，求上升序列 使得 最小。

思路

首先可以设 表示第 个数，上一个数为 ，转移显然。

然后我们做点转化，把上升序列变为不降序列，这样可以让我们的 DP 转移时不用在值域上平移，方法也非常简单，令 然后 ，这样 与 就是不降版本的原问题了。

写出转移式：

然后我们来观察我们的转移，我们注意到对每个 ，我们先在值域上加一个绝对值，然后再取前缀 。众所周知，绝对值是一个凸包，所以我们发现 是个凸包。

可以发现这个凸包是不增的（增的部分被前缀 抹掉了），我们每次加入绝对值时，顶点左边的部分斜率 ，右边 。然后我们发现这些顶点就是这个凸包的转折点，并且排序之后每个部分的斜率等于大于它的顶点的数量（的相反数）。

我们注意到其实我们不关心函数取值，而只关心这些转折点的位置，所以我们用个堆维护这些顶点，每次加入点的时候，因为右边斜率 ，所以可能会变成正的，于是我们把它扔掉（显然最多扔掉一个因为只 ）。然后此时整个函数的最小值的转折点就是最大的转折点，这时我们钦定当前的 为这个转折点即可。当然，聪明的你已经发现这可能不太对了，但是至少对于这个前缀而言，它是对的。

然后我们知道最终的那个取值是最重要的，所以它的 必然正确，然后向前扫，如果 ，那么显然合法，否则令 。因为在 的凸包中，越向左值越大，所以我们必然选取最右的点值。

我有点蠢了，这么显然的东西写了这么多。

CODE

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=1000010,FSIZE=1<<26;
ll n,a[N],b[N],ans;
priority_queue<ll> h;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1;i<=n;++i){
        read(b[i]);
        h.push(b[i]-=i);
        if(h.top()>b[i]){
            h.pop();
            h.push(b[i]);
        }
        a[i]=h.top();
    }
    for(int i=n-1;i;--i) a[i]=min(a[i],a[i+1]);
    for(int i=1;i<=n;++i) ans+=abs(a[i]-b[i]);
    printf("%lld\n",ans);
    for(int i=1;i<=n;++i) printf("%lld ",a[i]+i);
    return(0);
}