C-Making the Grade（线性DP，离散化，结论）

• 分两类：对单调上升和单调下降分别求一遍，取最小值即可

引理：在满足 S S S 最小的前提下，一定存在一种构造序列 B B B 的方案，使得 B B B 中数值都在 A A A 中出现过

（证明见 y y y总：AcWing 273. 分级 - AcWing）

• 有了这个结论，我们就可以将序列 A A A 中的元素离散化了（从小到大排序记录到数组 b b b ）

• f [ i ] [ j ] f[i][j] f[i][j] 表示构建前 i i i 个，以 b [ j ] b[j] b[j] 结尾的最优解

• 这题的优化方式 O ( n 3 ) O(n^3) O(n3) → rightarrow → O ( n 2 ) O(n^2) O(n2) 与 LCIS （线性DP，滚动数组）差不多

  都是将重复查询的过程优化（也可以用滚动数组优化掉一维数组）

#include 
using namespace std;

const int N=2005;
int a[N],b[N],f[N][N];
int solve(int n)
{
    for(int i=1;i<=n;i++)
    {
        int val=1e9;
        for(int j=1;j<=n;j++)
        {
            val=min(val,f[i-1][j]);
            f[i][j]=val+abs(a[i]-b[j]);
        }
    }
    int res=1e9;
    for(int i=1;i<=n;i++) res=min(res,f[n][i]);
    return res;
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i], b[i]=a[i];
    sort(b+1,b+1+n);
    int ans=solve(n);
    reverse(a+1,a+1+n);
    ans=min(ans,solve(n));
    cout<