前言

没有那么少。此专辑所有 DP 均指动态规划，非 DeePseek；DXD 均指丁小冬。

第一道：Bone Collector

链接：

1. 原题连接 （官方） ：hdu2602
2. 站内翻译版 （站内） ：BCOI-GF24骨头收藏家

尝试用 DXD 的方法分析题目（后两步为实现）。

1. 判断时是否能用 DP

其实这就是典型的 01背包了。

1. 无后效性： 假如现在选到第 $i$ 个骨头，那么剩下 $n-i$ 个骨头地选择情况并不会影响这一个骨头的选择。即在选剩下 $n-i$ 个骨头的时候，并不会回到这个 $i$ 修改答案。
2. 最优子结构： 在选第 $i$ 个骨头时选择最优的答案，最后的结果也会是最优的。
3. 重叠子问题： 要求前 $i$ 个骨头时的最大价值，就要先知道前 $i-1$ 个骨头的最大价值。

2. 定义状态变量

从问题出发。问题：用容量为 $V$ 的背包，在 $N$ 个物品中选择，如何使价值最大？

可以发现共有 $3$ 个变量，其中有一个是结果。所以可以定义 $dp_{i,j}=S_i$ 表示选择前 $i$ 个物品，背包容量为 $j$ 时的最大价值为 $S_i$。

3. 状态转移方程

在选择第 $i$ 件物品时，考虑选和不选两种情况。

1. 选：即为选前 $i-1$ 个物品的最大价值，此时背包容量要留出这个物品的体积，即 $j-w_i$。所以选的价值为：$dp_{i-1,j-w_i}$。
2. 不选：即选前 $i-1$ 个物品时的最大价值。即 $dp_{i-1,j}$ 。
3. 取较大值。

由于有两个变量，所以需要枚举这两个变量。一个 $i$ 循环枚举物品，$j$ 循环枚举背包容量。由于在选这一个物品的时候需要涉及到前一个物品的价值，所以 $i$ 需要递增循环。此时背包容量正序或倒序都可以。但是要注意 $j-w_i$ 可能为负数，所以在循环时要注意判断 $j≥w_i$。

4. 边界值和初始化

用 DXD 的方法，把状态转移方程的方程推到最前面。可以发现：

1. 需要涉及到 $i-1$，所以 $i$ 至少需要从 $1$ 开始。
2. 应为有 $j-w_i$，所以 $j$ 为 $[w_i,V]$。

由于要求最大值，所以所有内容都初始化为一个极小值 $0$。

5. 答案

就是 $dp_{N,V}$ 了。

6. 代码实现

略。

7. 问题及优化优化

1. 因为有多组测试数据，所以每次要清空 $dp$，否则你会得到教训。
2. 由于本题 $N\le1000$，所以这样的解法完全足够。但是也可以优化为一维。这样枚举背包容量的 $j$ 循环就要改为倒序。

第二道：ACboy needs your help

链接：

1. 原题链接：hdu1712。
2. 站内翻译版：BCOI-GF24ACboy需要你的帮助

其实这是经典的分组背包。把第 $i$ 门课看为第 $i$ 组，学习 $k$ 天就是第 $k$ 个物品。天数 $j$ 就是背包容量。第 $i$ 门课，学习 $k$ 天的价值为 $c_{i,k}$，物品体积为 $k$。接下来就按照分组背包的方法就好了。

第三题：宝物筛选

链接：

1. 原题链接：P1776 宝物筛选
2. 站内：BCOI-GF24宝物筛选

多重背包。但是直接提交会超时，需要二进制拆分（可以看下一题的题解）或单调队列优化。

第四题：砝码称重

链接：

1. 原题：P2347 [NOIP 1996 提高组] 砝码称重
2. 站内：BCOI【基础】砝码称重

暴力会超时。所以要用多重背包。题解：BCOI-O1626-solution。

第五题：Mowing the Lawn G

链接：

1. 原题：Mowing the Lawn G

定义 $dp_i$ 表示前 $i$ 个奶牛的最大效率。

在状态转移时选择不被选择的奶牛。

经过大量思考及翻阅题解，得出状态转移方程：

$$dp_i=\max\{dp_{j-1}+s_i-s_j\}$$

其中 $s$ 为 $a$ 的前缀和数组。

提交得 $40pts$。如何优化呢？其实我不是很懂。

首先这是适用于单调队列的 DP 的状态转移方程：

$$dp_i=\max/\min\{dp_j + a_i + b_i\}$$

然后我也不知道了。大概就是模版。

第六题：选择数字

链接：

1. 原题：P2034 选择数字

跟上一题一模一样，连样例都是一样的。