这是一篇dp的题解.题目是acwing 273.分级.
题目描述很简单哈.
题目:给定长度为N的序列A，构造一个长度为N的序列B，满足：
1、B非严格单调，即B1≤B2≤…≤BN或B1≥B2≥…≥BN。
2、最小化 S=∑Ni=1|Ai−Bi|。
只需要求出这个最小值S。
输入格式
第一行包含一个整数N。
接下来N行，每行包含一个整数Ai。
输出格式
输出一个整数，表示最小S值。
这个怎么做呢?首先我们得知道符合条件的Bi必定有一组是全部属于Ai的,证明很简单,我们把Ai排序变成Ci,假设我们当前有几组不在Ci,位于
Ci~Ci+1因为中间数变成它们并不影响其他数取值,假如当前这段的Ai比Ci+1大的为x,比Ci小的为y,那么当x=y怎么把这段移动都是不变的,而一旦大于小于则一定要移动.
有了这个性质就比较好dp了.因为有递增这个性质,我们设dp[i][j]为前i个,最后一个Bi为Cj,使得这样最小.
至于转移就是上一个最小且dp[i-1]转移过来的,因为我这里既然要取j当最后一个,那么后面的dp[i-1][>j]就不可取了,且前面取最小就好了QAQ.
递减也是一样的.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int dpa[N][N],dpb[N][N];
int a[N],b[N],c[N];
int main()
{
    int n,ans=2e9;
    cin>>n;
    for(int i=1;i<=n;i++)   {cin>>a[i];b[i]=a[i];c[i]=a[i];}
    sort(b+1,b+n+1);
    sort(c+1,c+n+1);
    reverse(c+1,c+1+n);
    for(int i=1;i<=n;i++)
    {
        int res=2e9;
        for(int j=1;j<=n;j++)
        {
            res=min(res,dpa[i-1][j]);
            dpa[i][j]=res+abs(a[i]-b[j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int res=2e9;
        for(int j=1;j<=n;j++)
        {
            res=min(res,dpb[i-1][j]);
            dpb[i][j]=res+abs(a[i]-c[j]);
        }
    }
    for(int i=1;i<=n;i++) ans=min(ans,min(dpa[n][i],dpb[n][i]));
    cout<<ans<<endl;
    return 0;
}