2024-05-14
算法题解
00

目录

题目
题目分析
观察
分析搜索和 dp 哪个好写
搜索
dp
dp 写法
总结

#dp #线性dp #经验总结

题目

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

简化版题目: 给定路径长度 NN,初始位置为 00,可以选择静止或向前移动若干单位,移动范围在 AABB 之间。最多可以移动 KK 次。路径上每个位置有若干数量的物品。求最多可以收集到的物品数量。

第一行包含一个整数 TT (1T101 \leq T \leq 10),表示测试用例的数量。
对于每个测试用例:

  • 第一行包含四个整数 N,A,B,KN, A, B, K (1ABN1001 \leq A \leq B \leq N \leq 1001KN1 \leq K \leq N)。
  • 第二行包含 NN 个整数 a1,a2,...,aNa_1, a_2, ..., a_N (1ai10001 \leq a_i \leq 1000),描述路径上每个位置的物品数量。

题目分析

观察

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

分析搜索和 dp 哪个好写

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

搜索

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

dp

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

dp 写法

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

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

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

cpp
if(i-o<0) continue;

总结

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

本文作者:CornWorld

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!