一个显然的事实：当b[]中的所有元素都出现在a[]中时，答案最小。
因此，不妨将a[]离散化到v[]，先不考虑降序（因为数据中没有降序，所以我程序里面也就没有打降序），接下来就是一个水水的二维动规了：
f[i][j]表示前i个元素升序，并且把a[i]改成v[i]的最小代价。那么就有：
f[i][j] = min(f[i-1][k])+abs(a[i]-v[j]) (k<=j)
显然min(f[i-1][k])可以记录下来，因此复杂度只有O(nm)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <cstdio>
#include <vector>
#include <algorithm>
int n, a[2001], f[2001][2001], g[2001][2001];
int main()
{
scanf("%d", &n);
std::vector<int> v;
for (int i = 1; i <= n; ++i)
{
scanf("%d", a+i);
v.push_back(a[i]);
}
std::sort(v.begin(), v.end());
int m = std::unique(v.begin(), v.end()) - v.begin();
for (int i = 1; i <= n; ++i)
{
g[i][0] = 0x7fffffff;
for (int j = 1; j <= m; ++j)
{
f[i][j] = g[i-1][j]+std::abs(v[j-1]-a[i]);
g[i][j] = std::min(g[i][j-1], f[i][j]);
}
}
printf("%d", g[n][m]);
}
|
