上升序列

Poj 3666

一条笔直的土路连接着FJ农场上的两个田地，但它改变的海拔比FJ想要的要多。他的牛不介意爬上或下一个斜坡，但他们不喜欢交替的山丘和山谷。FJ想要增加和清除道路上的泥土，这样它就变成了一个单调的斜坡(无论是向上倾斜还是向下倾斜)。 给你N个整数A1, … , AN (1 ≤ N ≤ 2,000) 描述海拔(0 ≤ Ai ≤ 1,000,000,000) 在路上N个等距的位置，从第一个字段开始，到另一个字段结束。FJ想把这些高度调整成一个新的序列B1, . … , BN 这要么是不增加的，要么是不减少的。由于增加或清除沿路任何位置的污物所需的费用相同，因此修路的总费用为 | A 1 - B 1| + | A 2 - B 2| + … + | AN - BN | 请计算他的道路分级的最低费用，使它成为一个连续的斜坡。FJ高兴地告诉你，有符号的32位整数肯定可以用来计算答案。

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer elevation: Ai

Output

* 第1行：一个整数，它是FJ对其土路进行分级的最小成本，因此它在高程上不会增加或减少。

Sample Input

7
1
3
2
4
5
3
9

Sample Output

3

使得序列非降，可以这么认为：dp[i][j]代表：前i个元素，第j大所花费的代价，定义一个b数组，代表a元素的上升序列（并非改变后的只是将a排个序），我们知道，第i个元素，第j大的代价一定是a[i]-b[j]，所以问题就简单了，只需要将j以前的最小的代价，加上当前i的代价就是我们要的答案，（因为，第i个元素，第j大，就要从前i-1给元素中找到不大于j的，才能保证递增，又要最小，所以找最小的满足条件的值就可，即: min(dp[i-1][k], k>=1 && k<=j)）,最后在扫一遍找到最小的就okk了

上代码（可以用滚动数组优化）

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=2e3+1;
const int inf=0x3f3f3f3f;
int dp[maxn][maxn],a[maxn],b[maxn];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        for(int i=1;i<=n;i++) {
            int tmp=inf;
            for(int j=1;j<=n;j++) {
                tmp=min(tmp,dp[i-1][j]);
                dp[i][j]=tmp+abs(a[i]-b[j]);
            }
        }
        int ans=inf;
        for(int i=1;i<=n;i++) {
            ans=min(ans,dp[n][i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}