P8817 [CSP-S 2022] 假期计划 解题笔记

给一个不用dp的做法

solution

考虑朴素做法。

预处理出 \(f(x)\)，表示距离 \(x\) 不超过 \(k\) 的点。

枚举每个景点 \(a\), \(b\), \(c\), \(d\)，通过预处理出的 \(f(x)\) 计算是否合法，更新答案。

这样时间复杂度是 \(O(n ^ 4)\) 的，不能通过本题。

考虑优化。