AcWing 273. 分级
原题链接
简单
作者:
牛奶小柒Luke
,
2021-02-05 21:05:06
,
所有人可见
,
阅读 399
//AcWing 273 分级
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2010;
const int MAX = 1e9;
int n;
int a[N],b[N];
int f[N][N];
int fun(){
int ans = MAX;
for(int i = 1;i <= n;++i){
b[i] = a[i];
}
sort(b + 1,b + n + 1);
for(int i = 1;i <= n;++i){
int MIN = MAX;
for(int j = 1;j <= n;++j){
MIN = min(MIN,f[i - 1][j]);
f[i][j] = MIN + abs(a[i] - b[j]);
}
}
for(int i = 1;i <= n;++i){
ans = min(ans,f[n][i]);
}
return ans;
}
int main(){
cin >> n;
for(int i = 1;i <= n;++i){
cin >> a[i];
}
int ans = fun();
reverse(a + 1,a + n + 1);
ans = min(ans,fun());
cout << ans << endl;
return 0;
}