#dp #线性dp #经验总结

题目

0Frog - 蓝桥云课 (lanqiao.cn)

简化版题目： 给定路径长度 $N$，初始位置为 $0$，可以选择静止或向前移动若干单位，移动范围在 $A$ 到 $B$ 之间。最多可以移动 $K$ 次。路径上每个位置有若干数量的物品。求最多可以收集到的物品数量。

第一行包含一个整数 $T$ ($1 \leq T \leq 10$)，表示测试用例的数量。
对于每个测试用例：

• 第一行包含四个整数 $N, A, B, K$ ($1 \leq A \leq B \leq N \leq 100$，$1 \leq K \leq N$)。
• 第二行包含 $N$ 个整数 $a_1, a_2, ..., a_N$ ($1 \leq a_i \leq 1000$)，描述路径上每个位置的物品数量。

题目分析

观察

1. 数据范围很水，写 $O(n^3)$ 都能随便过
2. 搜索看起来能过这个题目
3. 存在很显然的子问题拆分方法：如果已经通过 $K'$ 次移动到达位置 $N'$，此时子问题为 对于路径 $[N', N]$ / 最多可以移动 $K-K'$ 次 / 求最多可以收集到的物品数量
4. 对于 3. 提到的子问题，很显然无后效性且子问题重叠，那么这个题显然可以用 dp
5. 题目貌似只规定了起点，没规定终点（很重要，因为我交的第一发挂在这里了）

分析搜索和 dp 哪个好写

看起来写 dp 是愉快的选择~

搜索

因为子问题重叠，所以可以写个记忆化搜索。感觉答案空间还是比较好搜的（容易遍历），估计搜索函数部分 20 行以内可以解决。

dp

显然这个题目只需要写几个循环就行了，那不会超过 10 行。

dp 写法

最优状态很显然是可以收集到的物品的最大值。
我们先筛一下哪些状态对我们有用：到达某个点 $i$ 时，使用过 $j$ 次跳跃，此点的获得值应该为 $j-1$ 跳跃时的值加上此点的值。
那么很显然，这一切都与目前的位置 $i$ / 目前使用过跳跃的次数 $j$ 有关系，那就可以顺理成章的打出 $f_{i, j}$ 表示目前位置的状态。
转移方程可以先口胡一下再验证： $f_{i, j}=\max_{o=a}^{b}(f_{i-o, j-1})$
可以发现，这个题好像已经做完了（逃）
然后看到 $i-o$，就要注意一下越界的问题。最开始我写了这么样的代码：

cpp
int p=max(0, i-o);

试图给 $i-o<0$ 的部分进行转移，这显然是没有办法解释的操作（人类迷惑行为），实际上只需要不处理这部分即可：

cpp
if(i-o<0) continue;

总结

感觉这个题目主要难度还是在设计状态上面，太久不做 dp 题，根本没这种感觉 XD。