salesman | IOI2009

坐标轴上有 \(N\) 场展览会,每场展览会有一个举行时间 \(T_i\) ,举行地点 \(L_i\) 和获利 \(M_i\)

坐标向大移动 \(1\) 的代价是 \(D\),向小移动 \(1\) 的代价是 \(U\),速度为任意大。

每场展览会只能参加一次,问从 \(S\) 出发最后再回到 \(S\) 的最大获利。

\(N,T_i \le 5 \cdot 10^5,L_i \le 5 \cdot 10^5+1\)

先考虑一个弱化版的问题:\(T_i\) 互不相同。

\(f_i\)表示刚参加第 \(i\) 场展览会后的最大获利。

有转移方程 \(f_i = \max\limits_{T_j < T_i}f_j-cost(j,i)\)

其中 \[ cost(i,j)=\begin{cases} D(L_j-L_i) &(L_i<L_j)\\ U(L_i-L_j) &(L_i>L_j) \end{cases} \] 两种情况分别用树状数组维护前缀(后缀)最大值即可实现 \(O(\log n)\) 转移。

再考虑同一天的多场展览会怎么处理。

\(f_{i,0/1}\) 表示从左/右到达第 \(i\) 场展览会后的最大获利。

然后正反两遍 DP,每次用临时变量存由同一天的展览会转移来最优解,和树状数组中的最优解取个较优,计算出 DP 值后再把这一天所有展览会插入树状数组。

代码:

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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define upd(a, b) (a = max(a, b))
#define pb push_back

using namespace std;
const int N = 5e5 + 5;
int read() {
int c = getchar(), r = 0;
while(c < 48) c = getchar();
while(c > 47) r = r * 10 + c - 48, c = getchar();
return r;
}
int n, U, D, s, L[N], M[N], f[N][2];
vector <int> id[N];
struct BIT {
int c[N];
BIT() { rep(i, 1, N - 4) c[i] = INT_MIN; }
void ins(int i, int v) { for(; i <= N - 4; i += i & -i) upd(c[i], v); }
int qry(int i, int r = INT_MIN) { for(; i; i &= i - 1) upd(r, c[i]); return r; }
} Td, Tu;
void ins(int i, int v) {
Td.ins(i, v - (N - i) * D), Tu.ins(N - 3 - i, v - i * U);
}
int qry(int i) {
return max(Td.qry(i) + (N - i) * D, Tu.qry(N - 3 - i) + i * U);
}
int main() {
cin >> n >> U >> D >> s;
rep(i, 1, n) id[read()].pb(i), L[i] = read(), M[i] = read();
ins(s, 0);
rep(i, 1, N - 5) {
sort(id[i].begin(), id[i].end(), [](int a, int b) { return L[a] < L[b]; });
int pre = INT_MIN, suf = INT_MIN;
for(int j : id[i])
upd(pre, (f[j][0] = max(qry(L[j]), pre + (N - L[j]) * D) + M[j]) - (N - L[j]) * D);
for(auto j = id[i].rbegin(); j != id[i].rend(); j++)
upd(suf, (f[*j][1] = max(qry(L[*j]), suf + L[*j] * U) + M[*j]) - L[*j] * U);
for(int j : id[i]) ins(L[j], max(f[j][0], f[j][1]));
}
cout << qry(s);
return 0;
}