- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
-
- using namespace std;
-
- const int maxn = 2010, inf = 0x7fffffff;
- int a[maxn], n, f[maxn][maxn], b[maxn], ans;
-
- bool cmp(int a, int b)
- {
- return a > b;
- }
-
- int main()
- {
- scanf("%d", &n);
- for (int i = 1; i <= n; i++)
- {
- scanf("%d", &a[i]);
- b[i] = a[i];
- }
- for (int i = 1; i <= n; i++)
- f[i][0] = inf;
- sort(b + 1, b + 1 + n);
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- f[i][j] = min(f[i][j - 1], f[i - 1][j] + abs(a[i] - b[j]));
- ans = f[n][n];
- sort(b + 1, b + 1 + n, cmp);
- for (int i = 1; i <= n; i++)
- f[i][0] = inf;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- f[i][j] = min(f[i][j - 1], f[i - 1][j] + abs(a[i] - b[j]));
- printf("%d\n", min(ans, f[n][n]));
-
- return 0;
- }