呕呕呕呕呕 shai T4

· · 题解

题解

题解中出现的超纲算法仅助于理解，忽略这些句段不影响阅读。

考虑对于时间轴从小到大进行动态规划，令 f_i 表示在 [1,i] 这个时间段，安排跳舞机使用情况可以得到的最大收益。

显然有初始状态 f_0=0，对于 1\le i\le n，f_i 将会有以下几种转移：

为什么第二条是对的呢？可以发现一个玩家上台进行游玩的充分必要条件就是 [i-k+1,i] 这一段时间是这个玩家的空余时间的子集，也就是 i-k+1 \ge l_i 并且 i\le r_i。

那我们还有一个结论，我们一定会优先选择获得收益最高的玩家让他来游玩跳舞机。这个非常显然，用屁股都能想到。并且这个结论是对的，我们只关心我们获得的收益，而不是谁在游玩。

因此此算法正确性正确，我们得到了一个 O(nm) 的做法。

那么我们就需要解决的就是查询能包含 [i-k+1,i] 这个区间的收益最大值。首先能想到的可能是树套树来做二维偏序，因此我们就有了一个 O(m \log^2 n) 的做法。

这并不优秀。但是我们注意到我们动态规划的顺序是从小到大进行的，那么，我们可以维护一个全新的数据结构，不妨把这个数据结构叫做 S，在当前动态规划进行到 i 时，把所有左端点为 i-k+1 的玩家加入这个数据结构。

此时就会发现我们的式子简洁了许多，因为我们不需要关心 i-k+1 \ge l_j 这个限制了。这恰好就类似于扫描线的思想。

但是 i\le r_j 仍需要考虑，因此我们的数据结构可能还需要支持删除的操作。

来想一想我们需要求什么，我们要求的是最大值，那么我们能不能用优先队列（堆）来做这个事情呢？

每一次求解我们只需要关心最大值是否合法就可以了，因此在动态将玩家加入堆的过程之后，也就是要求解我们需要的 W 值，只需要判断堆顶的限制是否满足即可，如果不满足，就删除后再看最大值即可。

也许有人有疑问了，因为我们的数据结构中可能会有不合法的玩家没有被移出这个数据结构，但是这并不重要，只要我们的最大值合法就行，就算有不合法的玩家在这个数据结构中，这个玩家总有一次会被删除，即使不被删除也不会成为最大值，不会影响我们的求解。

这个操作很类似于对顶堆的操作。

时间复杂度是对的吗？这个同样非常显然，每一个玩家最多加入一次、删除一次，有点像单调队列的分析方式，因此时间复杂度 O(m \log n+n)。

代码

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

int n, m, k;
long long dp[500005];
vector<pair<int, int>> qj[500005];

signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        int l, r, w;
        cin >> l >> r >> w;
        if (l + k - 1 <= r)
        qj[l + k - 1].push_back({r, w});
    }
    dp[0] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> s;
    for (int i = 1; i <= m; ++i) {
        dp[i] = dp[i - 1];
        for (auto j : qj[i]) {
            s.push({-j.second, j.first});
        }
        while (!s.empty() && s.top().second < i) s.pop(); // 删除不合法的，也就是这个玩家已经离开了游戏厅
        if (!s.empty()) dp[i] = max(dp[i], dp[i - k] - s.top().first);
    }
    cout << dp[m] << "\n";
}

挑战最优解

此内容非题解主要内容。

  1. 将 vector 替换成链式前向星。
  2. 手写堆。
  3. 使用快读。
#include <bits/stdc++.h>
using namespace std;

struct Heap {
    pair<int, int> hp[500001];
    int tot = 0;

    inline void push(pair<int, int> x) {
        hp[++tot] = x;
        int i = tot;
        while (i > 1 && hp[i] < hp[i >> 1]) {
            swap(hp[i], hp[i >> 1]);
            i >>= 1;
        }
    }
    inline void pop() {
        int i = 1;
        swap(hp[i], hp[tot--]);
        while ((i << 1) <= tot) {
            int pos = i << 1;
            if (pos + 1 <= tot && hp[pos + 1] < hp[pos]) ++pos;
            if (hp[i] > hp[pos]) {
                swap(hp[i], hp[pos]);
                i = pos;
            } else return;
        }
    }
} s;

int n, m, k, nxt[500005], head[500005], cntt;
pair<int, int> to[500005];
long long dp[500005];

void add(int a, pair<int, int> b) {
    nxt[++cntt] = head[a];
    head[a] = cntt;
    to[cntt] = b;
}
namespace fastio
{
    const int bufl=1<<20;
    struct IN{
        FILE *IT=stdin;char ibuf[bufl],*is=ibuf,*it=ibuf;
        inline char getChar(){if(is==it){it=(is=ibuf)+fread(ibuf,1,bufl,IT);if(is==it)return EOF;}return *is++;}
        IN& operator>>(int &a){a=0;int b=0,c=getChar();while(c<48||c>57)b^=(c==45),c=getChar();while(c>=48&&c<=57)a=(a<<1)+(a<<3)+c-48,c=getChar();if(b)a=-a;return *this;}
    } fin;
}
#define cin fastio::fin
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) {
        int l, r, w;
        cin >> l >> r >> w;
        if (l + k - 1 <= r) add(l + k - 1, {r, w});
    }
    dp[0] = 0;
    for (int i = 1; i <= m; ++i) {
        dp[i] = dp[i - 1];
        while (head[i]) {
            s.push({-to[head[i]].second, to[head[i]].first});
            head[i] = nxt[head[i]];
        }
        while (s.tot && s.hp[1].second < i) s.pop();
        if (s.tot) dp[i] = max(dp[i], dp[i - k] - s.hp[1].first);
    }
    cout << dp[m] << "\n";
}

最大的点跑了 100 毫秒，应该是赛时最优解，或者是常数最小的正解。如果有疑问或者有更小常数的解法欢迎在评论中指出或者分享。