用dp，cost[i,j]记录将a[0...i]变成最后一个元素不大于j的sorted array所需要的最
小cost。求cost[i+1,j]时，考察包含a[i+1]（a[0...i+1]都变成不大于j）和不包含a[
i+1](去掉a[i+1]，将a[0...i]变成不大于j的数）两种情况下的cost，取较小值。。代
码如下，大家帮忙看看有没有错。思路和代码。
int minimum_cost(vector &v) {
if (v.size() <= 1) return 0;
int n = v.size();
map cost;
vector sorted(v);
sort(sorted.begin(), sorted.end());
vector::iterator it = unique(sorted.begin(), sorted.end());
sorted.resize(it-sorted.begin());
int newlen = sorted.size();
for (int j = 0; j < newlen; j ++) {
cost[sorted[j]] = (sorted[j] >= v[0] ? 0 : v[0] - sorted[j]);
}
for (int i = 1; i < n; i ++) {
int rev = cost[v[i]];
for (int j = newlen-1; j >= 0; j --) {
int with = rev;
if (sorted[j] < v[i])
with = cost[sorted[j]] + v[i] - sorted[j];
int without = cost[sorted[j]] + v[i];
cost[sorted[j]] = min(with, without);
}
}
int res = INT_MAX;
for (map::iterator iter = cost.begin(); iter !=
cost.end(); iter ++) {
res = min(res, iter->second);
}
return res;
}
