洛谷 P1759 分析（别看）

科技起源的小号1

2026-10-02 20:44:23

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：最大值与方案数

1.2 题目背景、允许、禁止与限制

背景：有 $n$ 个潜水工具，限重 $m$ ，最多阻力为 $v$ ，每个物品有其重量，阻力，潜水时长
允许：选若干个潜水工具使得在符合限重和限制阻力的情况下潜水时长最长且输出改答案下方案字典序最小的方案

1.3 题目数据范围与猜测

$1 \le n \le 100, 1\le m \le 200\longrightarrow O(nmm)$

1.4 一句话概括题意

有两个限制条件且含有回溯方案问题的0/1背包

2 题目破题推导

2.1 正向思维转逆向思维

既然题目要求字典序最小，我们就从“正序遍历”转为“逆序遍历”
然后对于新来的工具，如果上一个加这一个的状态大于等于本身答案，就更新答案序列
为什么？因为倒着来，先考虑的一定是字典序大的，然后如果新加进来的大于那就自然直接更新，但是如果新加进来的等于原答案呢？也会更新，这样正好能满足字典序最小的条件

3 模型匹配

关键词：动态求取最大值数 $\longrightarrow$ $\huge{背包dp}$
注意扩维，这样两个维度分别用于考虑限重及阻力
外加一个bool类型的take数组用于记录在考虑到第 $i$ 个物品，且背包剩余容量为 $j$ 和 $k$ ”这个特定状态下，是否选择第 $i$ 个物品

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int m, v, n;
const int N = 111, M = 222;
int a[N], b[N], c[N];
int dp[N][M][M];
bool take[N][M][M];

int main(){

    cin >> m >> v >> n;
    for (int i = 1;i <= n;i++){
        cin >> a[i] >> b[i] >> c[i];
    }
    memset(dp, -0x3f, sizeof(dp));
    for (int i = 0;i <= m;i++){
        for (int j = 0;j <= v;j++){
            dp[n + 1][i][j] = 0;
        }
    }
    for (int i = n;i >= 1;i--){
        for (int j = 0;j <= m;j++){
            for (int k = 0;k <= v;k++){
                dp[i][j][k] = dp[i + 1][j][k];
            }
        }
        for (int j = m;j >= a[i];j--){
            for (int k = v;k >= b[i];k--){
                if (dp[i + 1][j - a[i]][k - b[i]] + c[i] >= dp[i][j][k]){
                    dp[i][j][k] = dp[i + 1][j - a[i]][k - b[i]] + c[i];
                    take[i][j][k] = true;
                }
            }
        }
    }
    cout << dp[1][m][v] << endl;
    vector<int> ans;
    for (int i = 1;i <= n;i++){
        if (take[i][m][v]){
            ans.push_back(i);
            m -= a[i], v -= b[i];
        }
    }
    for (int now : ans){
        cout << now << " ";
    }
    
    return 0;
}