题目地址:http://poj.org/problem?id=3666

题目大意

给$N$个数$A_1, A_2, \cdots, A_N$,使其变成$B_1, B_2, \cdots, B_N$,$B$为不减或不增序列,使$|A_1-B_1|+|A_2-B_2|+\cdots+|A_N-B_N|$的值最小。

思路

将$A$升序得到$B$,易知$A_i$将变成$B$中的某一个数,设$dp[i+1][j]$为前$i$个数为不减序列,最后一个数为$B_j$的最小值。

得$dp[i+1][j] = min(dp[i][k], k \leq j) + |A[i] - B[j]|$

最后$min(dp[N][k], k \leq N)$即为答案。

AC代码

/*************************************************************************
    > File Name: 3666.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-13 二 21:07:39 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
int n;
int data[2005];
int des[2005];
int dp[2005][2005]; // 前i个数变成单调且最后一个数是des[j]

void solve() {
    memcpy(des, data, sizeof(data));
    sort(des, des+n);
    memset(dp, 0, sizeof(dp));
    for(int i=0; i<n; ++i) dp[0][i] = abs(data[0]-des[i]);

    for(int i=0; i<n; ++i) {
        int mincost = dp[i][0];
        for(int j=0; j<n; ++j) {
            mincost = min(mincost, dp[i][j]);
            dp[i+1][j] = mincost + abs(data[i]-des[j]);
        }
    }
    cout << *min_element(dp[n], dp[n]+n) << endl;

}

int main()
{
#ifdef Oj
    freopen("3666.in", "r", stdin);
#endif
    cin.sync_with_stdio(false);
    cin >> n;
    for(int i=0; i<n; ++i) cin >> data[i];
    solve();
    return 0;
}