突然高产
今天重温了一下没有做完的单调队列优化DP（结果发现什么也不会），然后就捡起了这道题练练手
假优化真暴力
n^3的暴力谁都会打，重点在怎么优化上，可以考虑先枚举j再枚举i，因为随着i的不断增加，i与j之间的距离是递增的，那么之前合法的决策现在也一定合法。然后k从j往1怼就行，顺便统计一下max(max=max(max,dp[j][k] + pnt[i].w)，然后dp[i][j] = max(dp[i][j],max)，这样就相当于结合了k-j中最大的情况。
然后再逆着跑一遍就行，但是不要直接Ctrl-C Ctrl-V正着的代码，判断距离时的等号方向不一样（别问我怎么知道的）
code:(注意：厌氧代码)
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
const int maxn(1010);
class POINT {
public:
int pos, w;
};
POINT pnt[maxn];
int dp[maxn][maxn];
bool cmp(POINT a, POINT b) { return a.pos < b.pos; }
int que[maxn], n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> pnt[i].pos >> pnt[i].w;
}
sort(pnt + 1, pnt + n + 1, cmp);
for (int i = 1; i <= n; i++) {
dp[i][i] = pnt[i].w;
}
for (int j = 1; j <= n; j++) {
for (int i = j + 1; i <= n; i++) {
int k = j, tmp = 0;
while (k >= 1 && pnt[j].pos - pnt[k].pos <= pnt[i].pos - pnt[j].pos) {
tmp = max(tmp, dp[j][k] + pnt[i].w);
k--;
}
dp[i][j] = max(dp[i][j], tmp);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
ans = max(ans, dp[i][j]);
}
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
dp[i][i] = pnt[n - i + 1].w;
}
for (int j = 1; j <= n; j++) {
for (int i = j + 1; i <= n; i++) {
int k = j, tmp = 0;
while (k >= 1 && pnt[n - j + 1].pos - pnt[n - k + 1].pos >=
pnt[n - i + 1].pos - pnt[n - j + 1].pos) {
tmp = max(tmp, dp[j][k] + pnt[n - i + 1].w);
k--;
}
dp[i][j] = max(dp[i][j], tmp);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
return 0;
}
|
另一种方法
题解上看到的一种叫2-points的算法（？，后来问了问沈队才知道这个玩意叫双指针，所以名字为啥不叫2-pointers。这个方法时间超短， $ O(n) $ 的时间复杂度
emmm…
找了篇文章看看