P5902 [IOI2009] Salesman

· · 题解

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;
}