题目内容

小塔正在游戏中进行一次有趣的探险，他第$0$天结束后在起点$0$位置，要安排接下来$1$~$t$天的行程、初始时每天最多可以选择前进$K$格。

沿途有一些特定的位置$x[i]$，在这些位置上小塔可以选择停下来获取增强，并且今天不再继续行进，可以使得之后每天能多行走$y[i]$格(也可以途径时不停下，选择继续进行今日的行程，但不会获得增强)。

一个位置可能有多个增强，小塔只能选择其中一个获得，即使再多停留一天也不能获得其他的增强效果。

小塔想知道在$t$天后，他最多能走到哪一位置。

思路

为了最大化行走的距离，直观的想法是尽量积累更多的增强，使得每天能行走的步数达到最大。然而，获得增强会导致当天的行走步数减少，因此不能直接贪心地获取所有增强。为此，我们使用动态规划来求解。

令状态 $dp[i][j]$ 表示在前 $i$ 天到达坐标 $j$ 时，所能积累的最大步数。对于每个坐标 $j$，如果存在多个增强，则选择其中最大的增强是最优的策略。因此，状态转移方程为：

$dp[i][j] = \max \{ \text{所有能到达} j \text{点的增强} \} + \text{当前位置的最大增强值（若无增强则为 0）}$

最终答案的求解公式为：