专栏文章

题解：AT_abc408_f [ABC408F] Athletic

tthis54
AT_abc408_f题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip5s4ks
此快照首次捕获于
2025/12/03 06:37
3 个月前
此快照最后确认于
2025/12/03 06:37
3 个月前
查看原文

朴素 dp

首先题目都明着告诉你能走的范围了，想到 dp 。 定义 dpidp_i为从i出发能走到最远的距离，显然 ans=max⁡dpians=\max{dp_i} ， 转移过程枚举在区间 [i−R,i−1][i-R,i-1] 与 [i+1,i+R][i+1,i+R]中所有 jj 满足 hi−hj≥Dh_i-h_j \ge D 的 dpjdp_j 去更新 dpidp_i，而因为更新时高度具有单调性，所有按照高度从小到大枚举 ii。
时间复杂度 O(NR)O(NR)。

线段树优化？

如果你熟练区间转移更新单点的dp，肯定想到使用线段树优化。现在的难点是，我们线段树中的值不一定都满足 hi−hj≥Dh_i-h_j \ge D 这个条件。我们发现，答案存进 dpdp 数组跟线段树没有关系，所以我们可以通过一些神奇的操作让更新到 ii 时线段树中 hi−hj<Dh_i-h_j < D 的 dpjdp_j 仍旧未更新，不难发现可以用一个队列来维护，每次更新时弹出队首更新线段树直到不满足 hi−hj≥Dh_i-h_j \ge D 或队列为空。
吐槽一句，因为题面说高度是 (1,2,…,N)(1,2,…,N) 的一个排列，所以更新到 ii 的时候有且仅有一个高度为 hi−Dh_i-D 的点能加入序列，所以根本就不用这个队列也能实现。
CPP
#include <bits/stdc++.h>
#define N 500010
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
int val[N << 2];
inline void mdf(const int& nw, const int& l, const int& r, const int& x, const int& k)
{
    if (l == r) return (void)(val[nw] = k);
    int mid = (l + r) >> 1;
    if (x <= mid) mdf(ls(nw), l, mid, x, k);
    else mdf(rs(nw), mid + 1, r, x, k);
    val[nw] = max(val[ls(nw)], val[rs(nw)]);
}//单点修改
inline int query(const int& pl, const int& pr, const int& l, const int& r, const int& x)
{
    if (pr < l || r < pl) return 0;
    if (pl <= l && r <= pr) return val[x];
    int mid = (l + r) >> 1;
    int ans = 0;
    if (pl <= mid) ans = max(ans, query(pl, pr, l, mid, ls(x)));
    if (mid < pr) ans = max(ans, query(pl, pr, mid + 1, r, rs(x)));
    return ans;
}//区间查询
int dp[N];
int h[N];
int s[N];//按照高度排序后的序列
int n, d, r;
int ans;
queue<int> q;//仍未处理的点
int main()
{
    cin >> n >> d >> r;
    for (int i = 1;i <= n;i++) cin >> h[i], s[i] = i;
    sort(s + 1, s + 1 + n, [](const int& x, const int& y)->bool {return h[x] < h[y];});
    for (int i = 1;i <= n;i++)
    {
        while (!q.empty() && h[s[i]] - h[q.front()] >= d) mdf(1, 1, n, q.front(), dp[q.front()]), q.pop();
        dp[s[i]] = query(s[i] - r, s[i] + r, 1, n, 1) + 1;
        q.push(s[i]);
        ans = max(ans, dp[s[i]]);
    }
    cout << ans - 1;//我们把起点看成走一步，最后应该减1
    return 0;
}

评论

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

正在加载评论...