本文共 656 字，大约阅读时间需要 2 分钟。

一条长度为L的路上有n个路灯，每个路灯能照亮的范围互不重叠。你要一边走路一边唱歌，每唱一首歌可以走p的路程。你必须唱完一首歌才能停下，歌唱一旦停止，至少经过t的路程才能继续唱。你不能在黑的地方唱歌。问最多能唱多少首歌。

很容易想到一个O(n^2)的动态规划算法。用f[i]表示走完第i个路灯能唱的歌数，用g[i]表示走完第i个路灯并唱完f[i]首歌能走到的位置。

状态转移方程：f[i] = f[j] + (r - max(l, g[j] + t)) / pg[i] = r - (r - max(l, g[j] + t)) % p

这样会在第14个点TLE，考虑把转移优化成O(1)的：如果i的答案不够优，我们就用i-1的答案代替i。

很显然，f和g都是单调不下降的。一个状态j可以被转移到i当且仅当g[j] + t ≤ r的最后一个状态。

我们每次只需要从j转移过来即可。除了x和y会被转移两次，其它都只会转移一次，所以时间复杂度是O(n)的。

另外需要注意当转移前后的f相等时，g更小的更优，要转移过去，否则会在第14个点WA。

初始化g[0] = -t，然后从i=1开始遍历每个路灯，计算f[i]和g[i]。

在计算过程中，使用循环来处理j的范围，并根据f[j]和g[j]的值来更新f[i]和g[i]。

最后，通过反向检查和调整，当f[i-1]不小于f[i]，并且g[i-1]不大于g[i]时，调整g[i]的值，以保证最优解。

这样优化后的算法不仅能够高效地解决问题，还能在处理大量数据时保持良好的性能。

转载地址：http://zqhfk.baihongyu.com/