Oiclass P1246 题解

你说为什么 01 背包模板不是偷东西呢？

额，搞错了，再来！

1. 划分阶段

一共划分 \(M\) 个阶段，每个阶段表示在这个阶段可以采的最多的草药

2. 确定状态和状态变量

状态变量就用一个二维数组 \(f\) 吧，也就是说 \(f_{i,\ j}\) 表示前 \(i\) 颗草药在前 \(j\) 的时间可以获得最大价值，也就是说我们想求的是用 \(j\) 的时间，如何在 \(a_{1 \to i}\) 的草药中获得最大价值，简单说就是他想赚多点钱

3. 写出状态转换方程并确定决策

这里我们现出不的写出一条状态转移方程： \[ f_{i,\ j} = \max\left(f_{i-1,\ j-t_{i}}+v_i,\ f_{i-1,\ j}\right)\ \ \ \ （\ t\ 数组为采药耗时，v\ 数组为草药价值\ ） \] 然后我们可以发现，如果 \(j<t_i\) 这个式子他就乱套了，数组下标怎么能是负的呢。所以我们需要特判一下 \(j<t_i\) 的情况，避免 RE 。那么在这种情况的时候，状态要怎么计算呢，我们可以发现，在这个时候，我们无法采摘新的草药，也就是说我们可以直接沿用 \(f_{i-1,\ j}\) 的情况。那么我们就可以写出完整地方程了： \[ f_{i,\ j} = \left\{\begin{array}{lr} j<t_i\ \ \ \ \ f_{i-1,\ j}\\ j≥t_i\ \ \ \ \ f_{i-1,\ j-t_{i}}+v_i \end{array}\right. \] 行，那么我们可以进行下一步了对..吧…..。额，这个方程看起来不够简洁优雅观察一下可以发现，实际上这个方程可以被压缩成一维的，这样可读性就高很多了。我们考虑一下，究竟是减掉可选物品呢？还是减掉时间呢？很明显，时间对我们来说更重要，所以我们尝试减掉物品这一维。我们首先直接无脑去掉他。发现会有一个问题，就是一个物品会有重复选择的问题。我们观察可以发现，如果我们这一步的操作是 \(f_{i,\ j} = f_{i-1,\ j}\) 的话，实际上就是直接复制了上一项的值，这里相信大家都是清楚的，那么如果我们这一步的操作是 \(f_{i,\ j} = f_{i-1,\ j-t_i}+v_i\) 的话这又意味着什么呢？仔细想一下，我们可以发现着意味着我们使用 \(t_i\) 的时间使得我们多得到了 \(v_i\) 的价值所以我们需要回退倒 只能选上一颗草药，只有 \(j-t_i\) 的时间 时的最优解然后在其基础上增加 \(v_i\) 的价值，所以我们发现实际上对我们有用的只有原数组的 \(j\) 下标，而 \(i\) 下标只是纯粹递增的而已。所以到这里，我们可以基本确定，我们的确可以去掉 \(i\) 下标，同时保持程序正常运行。那么你就会发现，虽然理论上可以，但是实际翻车了，这里是因为：我们在计算 \(f_j\ (\ 即\ f_{i,\ j}\ )\) 的时候，我们需要 \(f_{j-t_i}\ (\ 即\ f_{i,\ j-t_i}\ )\) 的值，而因为 \(j<j-t_i\) 所以如果我们按照正常的顺序遍历的方法，会造成一个结果被重复使用，也就是一颗草药被摘很多次的情况，很显然这是我们不想看到的，因此我们需要倒叙遍历这个数组，方程也就简化成这样了： \[ f_j=\left\{\begin{array}{lr} j<t_i\ \ \ \ \ f_j\\ j≥t_i\ \ \ \ \ f_{j-t_i}+v_i \end{array}\right. \]

而这条公式又可以简化成一行，同时不造成值的错误（尽管有些溢出的风险）： \[ f_j=\max(f_j,\ f_{j-t_i}+v+i) \] 终于搞完了

4. 初始条件

在什么时间都没有的情况下，我们不可能摘到草药，所以 \(f_0=0\) 而又因为数组的初始值就是 \(0\) 所以我们再次不需要进行任何操作，妙啊！！！！

5. 实现

直接模拟，上代码！：

#include <iostream>

using namespace std;

int times, m, t[109], v[109], f[10001];

int main() {
    cin >> times >> m;
    for (int i = 1; i <= m; i++) {
        cin >> t[i] >> v[i];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = times; j >= t[i]; j--) {
            f[j] = max(f[j], f[j - t[i]] + v[i]);
        }
    }
    cout << f[times];
}