题解

思路

把一次方案分成若干段连续打卡区间。若最后一次休息在第 $j$ 天，那么第 $j+1$ 天到当前挑战日 $x$ 连续打卡，要求 $x-j\le k$；挑战 $(x,y,v)$ 被满足当且仅当 $j<x-y+1$。

做法

子任务 1

枚举 $n$ 天的打卡集合，检查最长连续段和全部挑战，复杂度 $O(2^n(n+m))$。

子任务 2

令 dp[len] 表示处理到当前天、末尾连续打卡 len 天的最大能量。休息时转移到 len=0；打卡时从 len-1 转移并减去 $d$，再加入当天所有 $y_i\le len$ 的奖励。复杂度 $O(nk+m)$。

满分算法

在线段树中为可能的最后休息日 $j$ 维护

$$F(j)=\text{休息到 }j\text{ 时的最优值}+dj+\text{此后已满足的挑战奖励}.$$

处理挑战日 $x$ 前，先插入“第 $x$ 天休息”的状态。挑战 $(x,y,v)$ 的左端点为 $l=x-y+1$，它对所有 $j<l$ 的状态贡献 $v$，因此做一次前缀区间加。当天连续打卡结束的最优值为

$$\max_{x-k\le j<x}F(j)-dx.$$

只需离散化 $0$、每个 $x$、$x-1$、$l-1$ 和 $\max(0,x-k)$；其余日期没有挑战，休息状态的最优值不发生结构变化。

复杂度

• 子任务 1：$O(2^n(n+m))$；
• 子任务 2：$O(nk+m)$，空间 $O(k+m)$；
• 满分算法：$O(m\log m)$，空间 $O(m)$。

易错点

1. 挑战生效条件是 $j<l$，线段树更新到 $l-1$。
2. 同一天先插入休息状态，再加入当天挑战；休息当天不能获得该挑战。
3. 查询只允许 $j\ge x-k$，否则连续打卡超过 $k$ 天。
4. 答案至少为 $0$，因为可以一天也不打卡。