题面

FJ打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的 路面高度应当单调上升或单调下降，也就是说，高度上升与高度下降的路段不能 同时出现在修好的路中。

整条路被分成了N段，N个整数A1,…,AN(1<=N<=2,000)依次描述 了每一段路的高度(0<=Ai<=1,000,000,000)。FJ希望找到一个恰好含N个 元素的不上升或不下降序列B1,…,BN，作为修过的路中每个路段的高度。 由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为：

|A1−B1|+|A2−B2|+…+|AN−BN| 请你计算一下，FJ在这项工程上的最小支出是多少。FJ向你保证，这个支出 不会超过231−1。

输入 第1行: 输入1个整数：N

第2..N+1行: 第i+1行为1个整数：A_i

输出 第1行: 输出1个正整数，表示FJ把路修成高度不上升或高度不下降的最小花费 样例输入

7
1
3
2
4
5
3
9

样例输出 [复制]

3

提示 输出说明:

FJ将第一个高度为3的路段的高度减少为2，将第二个高度为3的路段的高度 增加到5，总花费为|2-3|+|5-3| = 3，并且各路段的高度为一个不下降序列 1,2,2,4,5,5,9。

解答

其实我没有想到怎么做。 首先要推出一个结论：最后的结果的序列中的数一定是原来序列中的数。证明嘛可以用我的口水话来证：

因为要求不严格单调，而原序列里面的数排个序也就不严格单调了。所以没有必要来在原来的基础上加一些数。。。

好了，我们来设计方程。这种题，肯定有个决策变量i表示当前计算到了第i个地方。那么，仅有这个变量够吗？足够表示所有高度信息吗？显然是不行的，因为前面已经对高度进行了修改，所以我们不知道前面的高度是多少，所以还需要维护一个高度的信息。我们再次发现，高度范围非常大，再加上之前的结论，所以我们可以考虑离散化！然后设计出方程式： \(dp[i][j] = min(dp[i-1][j]+abs(a[i]-b[j]),dp[i][j-1])\) $dp[i][j]$表示第i个地方的高度为小于等于第j高的高度的最小花费。可以从两个地方转移：

1. 前一个高度是j了，这一个也要变成j(因为不严格单调，所以变成j就可以了)那么，总花费是$dp[i-1][j]+abs(a[i]-b[j])$
2. 把这一个地方高度搞成j-1的最小花费，也就是说，基于之前的状态，现在不对这个地方进行修改

然后做一遍递增，再做一遍递减。比一下大小，这道题就完了 代码：

# include <cstdio>
# include <iostream>
# include <algorithm>
# include <stdio.h>
using namespace std;
const int MAXN = 2010;
int a[MAXN];
int b[MAXN];
bool cmp(const int &a,const int &b){return a>b;}
int dp[MAXN][MAXN];
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>a[i],b[i] = a[i];
    for(int i = 1;i<=n;i++)dp[i][0] = 999999999;//初始状态，搞大一点
    sort(b+1,b+n+1);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            dp[i][j] = min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]));
        }
    }

    int ans = dp[n][n];
    sort(b+1,b+n+1,cmp);
    for(int i = 1;i<=n;i++)dp[i][0] = 999999999;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            dp[i][j] = min(dp[i][j-1],dp[i-1][j]+abs(a[i]-b[j]));
        }
    }
    cout<<min(ans,dp[n][n]);
    return 0;
}