题解：P5902 [IOI 2009] Salesman

Kei__ · 2026-11-12 16:25:41 · 题解

先对每个展销会按开始时间排序，下文默认展销会已按时间顺序升序排列。

设 dp_i 表示参加完第 i 个展销会可以获得的最大利润，有转移方程：

对于 T_i=T_j 的情况，将这些展销会按 L_i 升序排序，参加这些展销会必然不会出现往返的情况，必然是从一个展销会 i 一直往左或者一直往右走到另一个展销会 j，或者不动。正反跑两遍即可。

直接这么做的复杂度是 O(n^2) 的，不能接受，考虑优化。

注意到转移式子里面的 -(L_i-L_j)D 可以拆成 -L_iD+L_jD，另一部分同理，其中 L_i 是独立的，可以提出去，这样我们就可以只维护 dp_j+L_jD 和 dp_j-L_jU 的前后缀最大值，以及单点修，BIT 维护即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5 , inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n , U , D , s , mt , md;
struct node {
  int d , v;
};
bool cmp(node x , node y) {
    return x.d < y.d;
}
basic_string<node>vs[N];
ll f[N] , g[N];
struct data {
    ll BIT[N];
    void into() {
        fill(BIT , BIT + md + 1 , -INF);
    }
    void add(int i , ll v) {
        for(; i <= md ; i += i & -i) BIT[i] = max(BIT[i] , v);
    }
    ll sum(int i) {
        ll mx = -INF;
        for(; i ; i -= i & -i) mx = max(mx , BIT[i]);
        return mx;
    }
    void clear(int i) {
        for(; i <= md ; i += i & -i) BIT[i] = -INF;
    }
}A , B , x , y;
int main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin >> n >> U >> D >> s;
    md = s;
    for(int i = 1 ; i <= n ; i ++) {
        int t , d , v;
        cin >> t >> d >> v;
        mt = max(mt , t) , md = max(md , d);
        vs[t].push_back({d , v});
    }
    A.into() , B.into() , x.into() , y.into();
    A.add(s , s * D) , B.add(md - s + 1 , -s * U);
    for(int i = 1 ; i <= mt ; i ++) {
        if(vs[i].empty()) continue;
        if(vs[i].size() == 1) {
            int d = vs[i][0].d , v = vs[i][0].v;
            ll now = max(A.sum(d) - d * D , B.sum(md - d + 1) + d * U) + v;
            A.add(d , now + d * D) , B.add(md - d + 1 , now - d * U);
        } else {
            sort(vs[i].begin() , vs[i].end() , cmp);
            for(int j = 0 ; j < vs[i].size() ; j ++) {
                int d = vs[i][j].d , v = vs[i][j].v;
                f[j] = max(max(A.sum(d) - d * D , B.sum(md - d + 1) + d * U) , max(x.sum(d) - d * D , y.sum(md - d + 1) + d * U)) + v;
                x.add(d , f[j] + d * D) , y.add(md - d + 1 , f[j] - d * U);
            }
            for(int j = 0 ; j < vs[i].size() ; j ++) {
                int d = vs[i][j].d;
                x.clear(d) , y.clear(md - d + 1);
            }
            for(int j = vs[i].size() - 1 ; ~j ; j --) {
                int d = vs[i][j].d , v = vs[i][j].v;
                g[j] = max(max(A.sum(d) - d * D , B.sum(md - d + 1) + d * U) , max(x.sum(d) - d * D , y.sum(md - d + 1) + d * U)) + v;
                x.add(d , g[j] + d * D) , y.add(md - d + 1 , g[j] - d * U);
            }
            for(int j = 0 ; j < vs[i].size() ; j ++) {
                int d = vs[i][j].d;
                x.clear(d) , y.clear(md - d + 1);
                A.add(d , max(f[j] , g[j]) + d * D) , B.add(md - d + 1 , max(f[j] , g[j]) - d * U);
            }
        }
    }
    cout << max(A.sum(s) - s * D , B.sum(md - s + 1) + s * U);
     return 0;
}