Making the Grade

题意：给定长度为的序列，构造一个长度为的序列，满足：

1. 非严格单调，即不递增或者不递减。
2. 最小化
   

思路：
这题数据弱，只考虑不递减的情况就可以过，但还要考虑不递增的情况比如我代码中的数据。

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

状态表示在完成前个数的构造时，，那么转移方程就是:

当然可以通过排序的方式对数组A进行简单的离散化来降低复杂度

MyCode:

#include <iostream>
#include <cstdio>
#include<algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=2e3+7,maxm=2e5+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn],b[maxn];
int f[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.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);
    for(int i=1; i<=n; ++i) {
        int val=1e9;
        for(int j=1; j<=n; ++j) {
            val=min(val,f[i-1][j]+abs(a[i]-b[j]));
            f[i][j]=val;
        }
    }
    int ans=1e9;
    for(int i=1;i<=n;++i) ans=min(ans,f[n][i]);
    for(int i=1; i<=n; ++i) {
        int val=1e9;
        for(int j=n; j; --j) {
            val=min(val,f[i-1][j]+abs(a[i]-b[j]));
            f[i][j]=val;
        }
    }
    for(int i=1;i<=n;++i) ans=min(ans,f[n][i]);
    cout<<ans<<'\n';
    return 0;
}
/*
7
9 3 5 4 2 3 1
*/