信竞学习笔记：[NOIP2023] 天天爱打卡

Tiger

发表于 2026-07-31

更新于 2026-07-31

学习笔记

6 1.7~2.1 分钟 752

注：这是本人的课堂笔记。

题目：P9871

题意概述

在第 $1 \sim n$ 天内跑步，跑步一天会消耗 $d$ 点能量值。不会连续跑步超过 $k$ 天，即不存在 $1 \leq x \leq n-k$ 使得在第 $x \sim x+k$ 天内均跑了步。有 $m$ 个挑战，每个挑战用一个三元组 $(x_i, y_i, v_i)$ 描述，表示在第 $x_i$ 天时，连续跑步至少 $y_i$ 天，会获得 $v_i$ 点能量值。求 $n$ 天后能获得的能量值的最大值。

数据范围：记 $l_i=x_i-y_i+1$ ， $r_i=x_i$ ，对于所有测试数据， $1\le t\le 10$ ， $1\le k\le n\le 10^9$ ， $1\le m\le 10^5$ ， $1\le l_i\le r_i\le n$ ， $1\le d,v_i\le 10^9$ 。

分析

首先想到暴力，枚举每天是否跑步，时间复杂度过高。

容易想到 DP。设 $dp_i$ 表示第 $1 \sim i$ 天可以获得的能量最大值，则最终答案是 $dp_n$ 。考虑连续跑的天数，枚举断点 $j$ ，表示从第 $j+1$ 天连续跑到第 $i$ 天（第 $j$ 天不跑），则 $j$ 的范围为 $[i-k, i-1]$ 。状态转移方程为：

dp_i = \max\limits_{j \in [i-k, i-1]} dp_{j-1} + w_{j+1,i} - (i-j)d

其中 $w_{j+1, i}$ 表示 $[j+1,i]$ 跑步区间提供到的总贡献。

考虑扫描线。对于枚举到的跑步区间 $[j, i]$ ，要使贡献区间 $[l_k, r_k]$ 贡献答案，则有 $j < l_k \leq r_k \leq i$ 。可以以右端点为下标将贡献区间加入，通过扫描线可以使区间天然满足 $r_k \leq i$ 。计算满足 $l_k > j$ 的贡献区间的贡献和。时间复杂度 $O(nk \log m)$ 。

由于 $n$ 的数值范围极大，考虑离散化。按照 $n$ 将贡献区间的左右端点进行离散化后再计算贡献。由于涉及到区间修改和区间最大值维护，考虑线段树。用线段树来维护 $dp_{j-1} + w_{j+1,i} - (i-j)d$ 的最大值。扫描线的过程中每次对这个值进行修改。时间复杂度 $O(m \log m)$ ，可以通过本题。

过程

前面的叙述可能过于抽象。下面给出程序运行过程的概述。

首先输入。输入的时候保存每个贡献区间及其左右端点。对左右端点进行离散化。随后遍历所有区间，按照右端点挂贡献区间。

随后进行扫描线和 DP。从左往右进行扫描线。对于每个点 $i$ ，首先将挂在 $i$ 下所有的贡献区间的贡献加入线段树，即在区间 $[0, l-1]$ 下加上 $v$ 的贡献。随后，减去对应消耗的能量值。统计 DP，也就是线段树上 $[i-k, i-1]$ 区间中的最大值。

最后输出 $dp_{len}$ 或 $ans$ （取决于如何维护 $dp$ 数组， $len$ 代表端点个数）。