AcWing 1020. 潜水员

题目传送门

一、题目理解

对于“考虑前\(i\)个物品，氧气体积大于等于\(j\)，氮气体积大于等于\(k\)的方案”的集合（\(f[i][j][k]\)）

可以按照“是否选择第\(i\)个物品”来划分
(1)若不选择第\(i\)个物品
则就是“考虑前\(i-1\)个物品，氧气体积大于等于\(j\) 并且氮气体积大于等于\(k\)的方案”的集合 (\(f[i-1][j][k]\))

(2)若选择了第\(i\)个物品
由于该集合均包含第\(i\)个物品
假设第\(i\)个物品有\(v_1\)个氧气 \(v_2\)个氮气
则除去第\(i\)个物品
就是考虑“从前\(i-1\)个物品选 氧气体积大于等于\(j-v_1\) 氮气体积大于等于\(k-v_2\)的方案”的集合

若\(j-v_1\)小于零的话
就说明第\(i\)个物品提供的氧气已经足够
不需要从前\(i-1\)个物品中获得任何氧气
因此当\(j-v_1\)小于零的时候
直接按照\(0\)考虑即可
氮气也一样

二、求最大值最小值初始化总结

二维情况

1、体积不超过\(j\)，\(f[i,k] = 0\)，\(0 <= i <= n, 0 <= k <= m\)（只会求价值的最大值）
并且当\(j-v<0\)时，状态没有意义。

2、体积恰好\(j\)，
当求价值的最小值：\(f[0][0] = 0\), 其余是\(INF\),当\(j-v<0\)时，状态没有意义。
当求价值的最大值：\(f[0][0] = 0\), 其余是\(-INF\),当\(j-v<0\)时，状态没有意义。

3、体积至少\(j\)，\(f[0][0] = 0\)，其余是\(INF\)（只会求价值的最小值）,当\(j?v<0\)时,状态有意义，需要从\(f[0]\)转移即可。

一维情况

1、体积不超过\(j\)，\(f[i] = 0, 0 <= i <= m\)（只会求价值的最大值）
并且当\(j-v<0\)时，状态没有意义。

2、体积恰好\(j\)，
当求价值的最小值：\(f[0] = 0\), 其余是\(INF\)
当求价值的最大值：\(f[0] = 0\), 其余是\(-INF\)

3、体积至少\(j\)，\(f[0] = 0\)，其余是\(INF\)（只会求价值的最小值）,状态有意义，需要从\(f[0]\)转移即可。

二、实现代码

#include 

using namespace std;
const int N = 1010; //气缸的个数上限
const int M = 100;  //需要的氧气、氮气上限值

int V1; //氧需要的量
int V2; //氮需要的量
int n;  //气缸的个数

int v1[N], v2[N], w[N];//第i个气缸里的氧和氮的容量及气缸重量
int f[M][M]; //DP数组

int main() {
    //读入氧需要的量，氮需要的量,气缸的个数
    cin >> V1 >> V2 >> n;
    //读入每个气缸的氧和氮的容量及气缸重量
    for (int i = 1; i <= n; i++) cin >> v1[i] >> v2[i] >> w[i];
    //求最小值要把除初始状态以外的所有状态初始化为+∞
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;
    //因为采用了降维，所以体积都是倒着的~
    for (int i = 1; i <= n; i++)
        for (int j = V1; j >= 0; j--)
            for (int k = V2; k >= 0; k--)
                f[j][k] = min(f[j][k], f[max(j - v1[i], 0)][max(k - v2[i], 0)] + w[i]);
    //输出
    printf("%d", f[V1][V2]);
    return 0;
}