自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:15:26，当前版本为作者最后更新于2023-03-08 14:50:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• Update on 2023.4.25：修改一处错误。

P5902 [IOI2009] Salesman

首先假设没有展览会在同一天。将展览会按 $T$ 从小到大排序，设 $f_i$ 表示参加第 $i$ 个展览会的最大收益，则有转移

$$f_i = \max_{1 \leq j < i} f_j - \mathrm{trans}(j, i) $$

其中若 $L_j \leq L_i$，则 $\mathrm{trans}(j, i) = D(L_i - L_j)$，否则等于 $U(L_j - L_i)$。分离贡献系数的 $i, j$，用两棵线段树维护即可。树状数组也可以维护，因为查询前后缀，且查询和修改都是取 $\max$。

对于在同一天的展览会，如果参加其中任何一个，则旅行商肯定是从某个位置较大的展览会走到某个位置较小的展览会，或者反过来，并参加其中所有展览会。将同一天的展览会按位置从小到大排序，分开做从前往后转移与从后往前转移即可。

注意考虑从家出发带来的影响。

时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool Mbe;
constexpr int N = 5e5 + 5;
constexpr int inf = 2e9 + 7;

int n, U, D, S;
struct exhi {
  int T, L, M;
  bool operator < (const exhi &z) const {
    if(T != z.T) return T < z.T;
    return L < z.L;
  }
} c[N];

struct SegTree {
  int val[N << 2];
  void build(int l, int r, int x) {
    val[x] = -inf;
    if(l == r) return;
    int m = l + r >> 1;
    build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
  }
  void modify(int l, int r, int p, int x, int v) {
    val[x] = max(val[x], v);
    if(l == r) return;
    int m = l + r >> 1;
    if(p <= m) modify(l, m, p, x << 1, v);
    else modify(m + 1, r, p, x << 1 | 1, v);
  }
  int query(int l, int r, int ql, int qr, int x) {
    if(ql <= l && r <= qr) return val[x];
    int m = l + r >> 1, ans = -inf;
    if(ql <= m) ans = max(ans, query(l, m, ql, qr, x << 1));
    if(m < qr) ans = max(ans, query(m + 1, r, ql, qr, x << 1 | 1));
    return ans;
  }
} fl, fr;
int query(int p) {
  int res = fl.query(1, N, 1, p, 1) - D * p;
  return max(res, fr.query(1, N, p, N, 1) + U * p);
}
void update(int p, int v) {
  fl.modify(1, N, p, 1, v + D * p);
  fr.modify(1, N, p, 1, v - U * p);
}


bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> U >> D >> S;
  for(int i = 1; i <= n; i++) cin >> c[i].T >> c[i].L >> c[i].M;
  sort(c + 1, c + n + 1);
  fl.build(1, N, 1), fl.modify(1, N, S, 1, D * S);
  fr.build(1, N, 1), fr.modify(1, N, S, 1, -U * S);
  for(int l = 1; l <= n; l++) {
    int r = l;
    while(r < n && c[r + 1].T == c[l].T) r++;
    static int f[N], g[N];
    for(int p = l; p <= r; p++) {
      g[p] = f[p] = query(c[p].L) + c[p].M;
    }
    for(int p = l + 1; p <= r; p++) {
      f[p] = max(f[p], f[p - 1] + c[p].M - D * (c[p].L - c[p - 1].L));
    }
    for(int p = r - 1; p >= l; p--) {
      g[p] = max(g[p], g[p + 1] + c[p].M - U * (c[p + 1].L - c[p].L));
    }
    for(int p = l; p <= r; p++) {
      update(c[p].L, max(f[p], g[p]));
    }
    l = r;
  }
  cout << query(S) << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}