主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：P9871 [NOIP2023] 天天爱打卡
最后更新于 2025-08-28 08:49:08
作者
2huk
分类
题解
题解
P9871
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
设 $f(i)$ 表示考虑前 $i$ 天，且第 $i$ 天一定不打卡的最大能量值。 转移枚举上一次不打卡的时间 $j$： $$ f(i) = \max_{j=\max(0,i-k-1)}^{i-1}f(j) - d(i-j-1)+w(j+1,i-1) $$ 其中 $w(x, y) = \sum_{x \le l_i \le r_i \le y}v_i$，即若 $x\sim y$ 都跑步能获得的奖励。 答案为 $\max_{i=1}^{n+1} f(i)$。这里上界取 $n+1$ 是因为有可能每天都打卡。 考虑优化。 对于 $w$，我们可以在枚举 $i$ 的过程中，用**数据结构**维护 $r_p \le i-1$ 的所有挑战 $p$。然后只需要查这里面 $l_p \ge j+1$ 的挑战即可。树状数组实现。当然最终正解并不用它。 令 $g(i) = f(i)+di$。则上面方程可以化成： $$ f(i)=d-di+\max_{j=\max(0,i-k-1)}^{i-1}g(j)+w(j+1,i-1) $$ 令 $h(j)=g(j) + w(j+1,i-1)$（$j \in[0, i-1]$）。考虑动态维护这个东西。 考虑求解 $i-1 \to i$ 的增量。 首先要将所有 $r_p = i-1$ 的挑战 $p$ 的贡献加入。具体的，我们需要将 $h(0),h(1),\dots h(l_p-1)$ 整体加 $v_p$。 然后 $h(i-1) \gets g(i-1)+w(i,i-1)=g(i-1)$。这是一个单点修改。相当于修改了 $h$ 的定义域。 然后还需要查 $h$ 的区间最大值。 线段树维护 $h$ 即可。 时间复杂度 $\mathcal O(n \log n)$。考虑优化。 好吧我也没太看懂优化在干啥。反正就是离散化后变成 $\mathcal O(m \log m)$。
正在渲染内容...
点赞
2
收藏
0
