专栏文章

P5902

NNygglatho
P5902题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip02o47
此快照首次捕获于
2025/12/03 03:57
3 个月前
此快照最后确认于
2025/12/03 03:57
3 个月前
查看原文
令 dpt,idp_{t,i} 表示时间为 tt，此时在 ii 结束的最大利润，mt,im_{t,i} 表示时间 tt 时 ll 点展销会的盈利，若不存在展销会则 mt,im_{t,i} 为 00。显然最后答案为 max⁡(max⁡{dpTmax⁡,i+D×(S−i)∣i<S},max⁡{dpTmax⁡,i+U×(i−S)∣i≥S})\max(\max\{dp_{T_{\max},i}+D\times (S-i)\mid i<S\},\max\{dp_{T_{\max},i}+U\times (i-S)\mid i\ge S\})。
先考虑没有两个展销会在同一天举行的情况。
转移分在上游和在下游转移，即：
  • dpt,0={U×(S−i)i<SD×(i−S)i≥Sdp_{t,0}=\begin{cases}U\times (S-i)& i<S\\D\times (i-S)& i\ge S\end{cases}
  • ∀i>0,dpt,i=max⁡(dpt−1,i,max⁡{dpt−1,j+D×(i−j)∣j<i},max⁡{dpt−1,j+U×(j−i)∣j>i})\forall i>0,dp_{t,i}=\max(dp_{t-1,i},\max\{dp_{t-1,j}+D\times (i-j)\mid j<i\},\max\{dp_{t-1,j}+U\times (j-i)\mid j> i\})。
然后考虑存在的情况。
显然一天内肯定是只朝一个方向走是最优的。
那么考虑分从上游到下游转移和从下游到上游转移。
令 ft,if_{t,i} 表示钦定上游到下游转移，gt,ig_{t,i} 表示钦定从下游到上游转移，时间为 tt，此时在 ii 结束的最大利润，有：
  • ft,i=max⁡(dpt−1,i,max⁡{ft,j+D×(i−j)∣j<i},max⁡{dpt−1,j+U×(j−i)∣j>i})f_{t,i}=\max(dp_{t-1,i},\max\{f_{t,j}+D\times (i-j)\mid j<i\},\max\{dp_{t-1,j}+U\times (j-i)\mid j> i\})。
  • gt,i=max⁡(dpt−1,i,max⁡{dpt−1,j+D×(i−j)∣j<i},max⁡{gt,j+U×(j−i)∣j>i})g_{t,i}=\max(dp_{t-1,i},\max\{dp_{t-1,j}+D\times (i-j)\mid j<i\},\max\{g_{t,j}+U\times (j-i)\mid j>i\})。
  • dpt,i=max⁡(ft,i,gt,i)dp_{t,i}=\max(f_{t,i},g_{t,i})。
这样是 O((Lmax⁡)2×Tmax⁡)O((L_{\max})^2\times T_{\max}) 的，考虑优化。
首先显然 dptdp_t 是只和 dpt−1dp_{t-1} 有关的，因此可以滚动数组把 tt 这一维删掉。然后就可以用四个线段树分别维护 max⁡{fj+D×(i−j)},max⁡{dpj+U×(j−i)},max⁡{dpj+D×(i−j)},max⁡{gj+U×(j−i)}\max\{f_{j}+D\times (i-j)\},\max\{dp_{j}+U\times (j-i)\},\max\{dp_{j}+D\times (i-j)\},\max\{g_{j}+U\times (j-i)\}，因为 D×(i−j),U×(j−i)D\times (i-j),U\times (j-i) 的相对大小是不改变的，每次只需要整体修改这个，查询合法部分的 max⁡\max，加入 fjf_j 和 gjg_j。最后再更新 dpjdp_j，这样就把复杂度降到了 O(Lmax⁡log⁡(Lmax⁡)×Tmax⁡)O(L_{\max}\log (L_{\max})\times T_{\max})。
然后可以发现对于 jj 只需要在存在展销会的这几天更新 dpjdp_j。否则更新 dpjdp_j 时假如从 kk 转移到 jj，显然转移时直接找 dpkdp_k 转移一定比找 dpjdp_j 转移不劣，统计答案时同理。
那么只需要在线段树里存下 dpjdp_j 的值，然后令 fj,gj←dpjf_j,g_j\gets dp_j，如果这一天 jj 存在展销会，那么就更新 fj,gj,dpjf_j,g_j,dp_j，同时更新线段树里的值。复杂度 O(nlog⁡Lmax⁡)O(n\log L_{\max})。常数略大。
CPP
struct Info {
    int l; ll m;
} ;

vector <Info> v[N];
int n, s;
ll u, d;
constexpr int w = 500005;
ll dp1[N], dp2[N], dp[N], tmp[N];
struct Sgt {
    ll d[N << 2], b[N << 2];
    void Pd (int l, int r, int p) {
        int m = (l + r) >> 1;
        d[p << 1] += b[p], d[p << 1 | 1] += b[p], b[p << 1] += b[p], b[p << 1 | 1] += b[p], b[p] = 0LL;
    }
    void Add (int l, int r, int s, int t, int p, ll v) {
        if (l <= s && t <= r) {
            d[p] += v;
            b[p] += v;
            return ;
        }
        int m = (s + t) >> 1;
        Pd (s, t, p);
        if (l <= m) Add (l, r, s, m, p << 1, v);
        if (m < r) Add (l, r, m + 1, t, p << 1 | 1, v);
        d[p] = max (d[p << 1], d[p << 1 | 1]);
    }
    ll Qry (int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) return d[p];
        int m = (s + t) >> 1;
        Pd (s, t, p);
        ll res = -inf;
        if (l <= m) res = Qry (l, r, s, m, p << 1);
        if (m < r) res = max (res, Qry (l, r, m + 1, t, p << 1 | 1));
        return res;
    }
    void Update (int x, ll v) {
        ll tmp = Qry (x, x, 0, w, 1);
        Add (x, x, 0, w, 1, v - tmp);
    }
} st1, st2; // 这里开的线段树重复使用，所以只开了两颗
int main () {
    // OPEN
    IOS
    cin >> n >> u >> d >> s;
    F (i, 1, n) {
        int t, l, m;
        cin >> t >> l >> m;
        v[t].push_back ({l, m});
    }
    int ls = s;
    F (i, 0, w) {
        if (i < s) dp[i] = - u * (s - i);
        else dp[i] = - d * (i - s);
        dp1[i] = dp2[i] = -inf;
    }
    F (i, 0, w) st1.Add (i, i, 0, w, 1, - d * (ls - i) + dp[i]);
    F (i, 0, w) st2.Add (i, i, 0, w, 1, - u * (i - ls) + dp[i]);
    F (t, 1, 500000) {
        sort (v[t].begin (), v[t].end (), [] (Info x, Info y) {return x.l < y.l; });
        for (auto [l, m] : v[t]) tmp[l] = dp[l];
        for (auto [l, m] : v[t]) {
            st1.Add (0, w, 0, w, 1, d * (ls - l));
            st2.Add (0, w, 0, w, 1, u * (l - ls));
            ls = l;
            ll tmp1 = dp1[l];
            dp1[l] = max (st1.Qry (0, l - 1, 0, w, 1), st2.Qry (l + 1, w, 0, w, 1)) + m;
            st1.Update (l, max (dp1[l], tmp1));
            st2.Update (l, max (dp1[l], tmp1));
        }
        for (auto [l, m] : v[t]) st1.Update (l, tmp[l] - d * (ls - l)), st2.Update (l, tmp[l] - u * (l - ls));
        sort (v[t].begin (), v[t].end (), [] (Info x, Info y) {return x.l > y.l; });
        for (auto [l, m] : v[t]) {
            st1.Add (0, w, 0, w, 1, d * (ls - l));
            st2.Add (0, w, 0, w, 1, u * (l - ls));
            ls = l;
            ll tmp1 = dp2[l];
            dp2[l] = max (st1.Qry (0, l - 1, 0, w, 1), st2.Qry (l + 1, w, 0, w, 1)) + m;
            st1.Update (l, max (dp2[l], tmp1));
            st2.Update (l, max (dp2[l], tmp1));
        }
        for (auto [l, m] : v[t]) dp[l] = max (dp[l], max (dp1[l], dp2[l]));
        for (auto [l, m] : v[t]) st1.Update (l, dp[l] - d * (ls - l)), st2.Update (l, dp[l] - u * (l - ls));
        for (auto [l, m] : v[t]) dp1[l] = dp2[l] = -inf;
    }
    ll ans = 0LL;
    F (i, 1, 500000) {
        if (i < s) ans = max (ans, dp[i] - d * (s - i));
        else ans = max (ans, dp[i] - u * (i - s));
    }
    cout << ans << '\n';
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...