[P1759 通天之潜水]

Re_FYCCCCTA · 2023-07-31 10:16:43 · 题解

原题

思路

很明显是一道 01 背包。设 f_{i , j} 表示总重量为 i，总浮力为 j 时所能支撑的最长时间，那么状态转移方程为：f_{i , j} = \max(f_{i , j} , f_{i - a , j - b} + c)，a，b，c 分别为当前这件物品的重力，阻力和能支撑的时间，而 f_{m , v} 就是题目中所要求的最多能支撑的时间。

背包问题详解

但本题需输出具体的方案，还需要保证字典序最小，因此可以用字符串来存储，具体来说，定义一个二维数组（以下称为 s 数组）记录转移数组每一种状态所对应的方案，并在转移时更新，这样既方便添加（直接将数字转换成所对应的字符）又方便比较。注意要保证字典序最小，因此在 f_{i , j} = f_{i - a , j - b} + c 时要从 s_{i , j} 和 s_{i - a , j - b} + c 中选最小的。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXM = 200;
int m , v , n , a[MAXN + 5] , b[MAXN + 5] , c[MAXN + 5] , f[MAXM + 5][MAXM + 5];
string s[MAXM + 5][MAXM + 5];
int main()
{
    cin >> m >> v >> n;
    for (int i = 1 ; i <= n ; i++)
        cin >> a[i] >> b[i] >> c[i]; 

    for (int i = 1 ; i <= n ; i++)
        for (int j = m ; j >= a[i] ; j--)
            for (int k = v ; k >= b[i] ; k--)
            {
                char ci = (char)i;
                if (f[j][k] < f[j - a[i]][k - b[i]] + c[i])
                {
                    f[j][k] = f[j - a[i]][k - b[i]] + c[i];
                    s[j][k] = s[j - a[i]][k - b[i]] + ci;
                }
                else if (f[j][k] == f[j - a[i]][k - b[i]] + c[i] && s[j - a[i]][k - b[i]] + ci < s[j][k])
                    s[j][k] = s[j - a[i]][k - b[i]] + ci;
            }
    cout << f[m][v] << endl;
    for (int i = 0 ; i < s[m][v].size() ; i++)
        cout << s[m][v][i] - 0 << ' ';
    return 0;
}