题目描述
https://www.luogu.com.cn/problem/P2893
简单dp复习
Solution
首先能够发现可以离散化
我们令f[i][j]为前i条路，第i条路的高度是j的最小值
转移直接枚举最小的f[i-1][k]即可，只需要额外维护一下即可
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 2010
#define ll long long
#define INF 100000000000000000ll
using namespace std;
int n, a[maxn];
int b[maxn], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = a[i];
sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
}
ll f[maxn][maxn], minf[2][maxn];
ll ans = INF;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
init_hash();
for (int i = 1; i <= n; ++i) {
int t1 = i & 1, t2 = t1 ^ 1; minf[t1][0] = INF;
for (int j = 1; j <= cnt; ++j) {
f[i][j] = minf[t2][j] + abs(a[i] - b[j]));
minf[t1][j] = min(minf[t1][j - 1], f[i][j]);
}
}
for (int i = 1; i <= cnt; ++i) ans = min(ans, f[n][i]);
for (int i = 1; i <= n; ++i) {
int t1 = i & 1, t2 = t1 ^ 1; minf[t1][cnt + 1] = INF;
for (int j = cnt; j; --j) {
f[i][j] = minf[t2][j] + abs(a[i] - b[j]));
minf[t1][j] = min(minf[t1][j + 1], f[i][j]);
}
}
for (int i = 1; i <= cnt; ++i) ans = min(ans, f[n][i]);
cout << ans << endl;
return 0;
}
|