P12247 跳舞机 题解

· · 题解

45 pts

不难想到 dp。

定义状态 dp_i 表示，前 i 分钟兴奋值之和的最大值。

转移时枚举玩家 j，转移方程为：

\begin{cases}dp_i \leftarrow \min(dp_i,dp_{i-1}) \\ dp_i \leftarrow \min(dp_i,dp_{i-k}+w_j) & l_j \le i-k+1\;\mathrm{and}\;i \le r_j\end{cases}

直接转移的复杂度为 O(n^2)（视 n,m 同阶），期望得分 45。

100 pts

考虑如何优化转移，容易想到使用优先队列。

先将玩家按 l_i 升序排列。

每次转移前，将当前满足条件的玩家出队，并将不满足条件的玩家出队，之后选择当前队首，即 w_i 最大的玩家，进行转移即可。

复杂度 O(n \log n)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 10;
struct Node{
    int l, r, w;
}a[MAXN];
bool cmp(Node x, Node y){
    return x.l < y.l;
}
int dp[MAXN];
priority_queue <pair<int, int>> q;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1;i <= n;i++) cin >> a[i].l >> a[i].r >> a[i].w;
    sort(a + 1, a + n + 1, cmp);
    int cur = 1;
    for (int i = 1;i <= m;i++){
        dp[i] = dp[i - 1];
        while (cur <= n && a[cur].l <= i - k + 1){
            if (a[cur].r >= i) q.push({a[cur].w, a[cur].r});
            cur++;
        }
        while (!q.empty() && q.top().second < i) q.pop();
        if (i >= k && !q.empty()) dp[i] = max(dp[i], dp[i - k] + q.top().first);
    }
    cout << dp[m] << endl;
    return 0;
}