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)

。

CPP

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

文章操作

45 pts

100 pts

相关推荐

评论

P12247 跳舞机题解