「背包DP」科技庄园

本题为3月17日23上半学期集训每日一题中A题的题解

题面

题目描述

Life种了一块田，里面种了有一些桃树。

Life对PFT说：“我给你一定的时间去摘桃，你必须在规定的时间之内回到我面前，否则你摘的桃都要归我吃！”

PFT思考了一会，最终答应了！

由于PFT的数学不好！它并不知道怎样才能在规定的时间获得最大的价值，

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life。同时PFT每次只能摘一棵桃树，，每棵桃树都可以摘K次（对于同一棵桃每次摘的桃数相同）。每次摘完后都要返回出发点（PFT一次拿不了很多）即Life的所在地（0，0）(试验田左上角的桃坐标是（1，1）)。

PFT每秒只能移动一个单位，每移动一个单位耗费体力1(摘取不花费时间和体力,但只限上下左右移动)。

输入

第一行：四个数为N，M，TI，A 分别表示试验田的长和宽，Life给PFT的时间，和PFT的体力。

下面一个N行M列的矩阵桃田。表示每次每棵桃树上能摘的桃数。

接下来N行M列的矩阵，表示每棵桃最多可以采摘的次数K。

输出

一个数：PFT可以获得的最大的桃个数。

样例输入

4 4 13 20
10 0  0  0
0  0  10 0
0  0  10 0
0  0  0  0
1 0 0 0
0 0 2 0
0 0 4 0
0 0 0 0

样例输出

10

提示

样例说明：

可以摘到1次（1，1）和1次（2，3），体力和时间不满足再摘桃了。

范围：

对于30%的数据: $ 10 \leq M，N，TI，A \leq 50 $

对于100%的数据: $ 10 \leq M，N，TI，A \leq 100 $

此外对于100%的数据: $ 10 \leq k \leq 100 $

保证结果在long int范围内

思路分析

本题的题意就是让你在规定的时间限制和体力限制里摘更多的果子.如果我们把一棵树看成一个物品,把这棵树每次可以摘的果子看成它的价值,把这棵树可以摘的次数看成它的数量,把走到这棵树然后走回需要的时间(或体力,显然两者等值,注意要一来一回)看作商品占用的空间(由题意,此处需要的时间就是这个点到起点的曼哈顿距离),那么这就是一个经典的多重背包的模型.背包的容量就是两个限制的最小值(因为每走一步两个限制其实是一样的).此题数据量较小,直接使用朴素的多重背包即可完成.

不过这题有两个坑点一定要注意,第一是题目明确说明了:

他不想摘很多的桃以至体力为0

所以体力与时间不同,不能减小为0,所以体力实际上的限制量是要减一的.第二是这题是可能出现一颗果树不让摘的情况的,所以需要把第一个矩阵离线下来,在两个矩阵同一位置均不为0的时候,再处理成物品.

如果你还不会朴素多重背包,请先阅读背包九讲(如果打不开github也可以在集训队的群文件中搜索),或者这篇博客(可能需要一点魔法才能访问)进行学习,当然也可自行搜索博客等学习.在ACWing上有公开的朴素多重背包的板子题,请尝试独立通过此题,然后再来做这道题.

参考代码

时间复杂度: \(O(min{TI,A}NMK)\)(K为总共可摘果子数)

空间复杂度: \(O(min{TI,A}NM)\)

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, t, a;
    cin >> n >> m >> t >> a;
    int lit = min(t, a - 1); // 计算背包容量(注意体力不能为0,所以这里要减一)

    // 离线第一个矩阵,以便和第二个矩阵对比
    vector<vector<int>> gA(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> gA[i][j];
        }
    }

    // 将输入的信息转换为背包问题中对应的信息
    int *cost = new int[n * m + 1]; // 物品占用空间
    int *val = new int[n * m + 1]; // 物品价值
    int *cnt = new int[n * m + 1]; // 物品数量
    int idx = 0; // 上述数组的统一下标,同时记录总数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int b;
            cin >> b;
            if (gA[i][j] && b) { // 当前位置有一颗能摘的果树
                cost[++idx] = i + j << 1; // 注意一来一回,所以要*2(<<1等价于*2,注意优先级)
                val[idx] = gA[i][j];
                cnt[idx] = b;
            }
        }
    }

    // 朴素多重背包模板(建议还是用空间压缩的,因为朴素的反而容易错)
    vector<vector<i64>> dp(idx + 1, vector<i64>(lit + 1, 0));
    for (int i = 1; i <= idx; i++) {
        for (int j = 1; j <= lit; j++) {
            for (int k = 0; k <= cnt[i]; k++) { // 别从1开始,需要先复制前一层
                if (j - k * cost[i] >= 0) {
                    dp[i][j] =
                        max(dp[i][j], dp[i - 1][j - k * cost[i]] + k * val[i]); // 别写成dp[i - 1][j],因为前面可能已经更新了当前的dp[i][j]
                } else {
                    break;
                }
            }
        }
    }

    cout << dp[idx][lit] << "\n";

    delete[] val;
    delete[] cost;
    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德