经过一系列的玄学证明,是可以证到$B$数组的值全来自于$A$数组的值。

递增的大概是这样的:

  • 数学归纳法。命题对$N=1$成立。
  • 假设$N=k-1$已经成立。对于$B_{k-1}\le A_k$,直接令$B_k=A_k$,显然成立。
  • 否则,要么令$B_k=B_{k-1}$,命题依旧成立。要么存在一个$j$,使 $B_j,B_{j+1},\cdots ,B_k$ 为同一个值$val$,那么可以转化为一个货仓选址问题,也就是在 $A_j,A_{j+1},A_{j+2},\cdots ,A_k$ 取一个数$mid$,若$mid>=B_{j-1}$,令$B_k=mid$,否则令$B_k=B_{j-1}$。

无论如何,都成立,证毕,然后利用这个性质,
把以下DP式简化:
$f_{i,j}=\max\limits_{k\le j}\{f_{i-1,k} \}+abs(a[i]-j)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=2e3+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll f[N][N];int arr[N],a[N],n,len;
void disc()
{
    sort(arr+1,arr+n+1);len=0;
    for(int i=1;i<=n;i++)
        if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
}
int main()
{
    qr(n);
    for(int i=1;i<=n;i++)qr(a[i]),arr[i]=a[i];
    disc();
    for(int i=1;i<=n;i++)
    {
        f[i][1]=f[i-1][1]+abs(a[i]-arr[1]);
        int k=1;
        for(int j=2;j<=len;j++)
        {
            if(f[i-1][k]>f[i-1][j])k=j;
            f[i][j]=f[i-1][k]+abs(a[i]-arr[j]);
        }
    }
    ll ans=1e12;
    for(int i=1;i<=len;i++)ans=min(ans,f[n][i]);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        f[i][len]=f[i-1][len]+abs(a[i]-arr[len]);
        int k=len;
        for(int j=len-1;j;j--)
        {
            if(f[i-1][k]>f[i-1][j])k=j;
            f[i][j]=f[i-1][k]+abs(a[i]-arr[j]);
        }
    }
    for(int i=1;i<=len;i++)ans=min(ans,f[n][i]);
    qw(ans);puts("");
    return 0;
}