2021CCPC闯关游戏

dp 分组背包 T3

ZZULIOJ

小i正在玩一个闯关游戏，游戏一共$n$关。

初始的时候小$i$有$H$点体力以及$0$个金币。

小$i$只能按从第$1$关到第$n$关按顺序完成。在第$i$关时，小$i$要在三种操作中选择一种：

1.当前体力不小于$A_i$可以选择这个操作，消耗$A_i$点体力，获得$B_i$个金币。

2.当前体力不小于$C_i$可以选择这个操作，消耗$C_i$点体力，获得$D_i$个金币。

3.结束游戏，直接结算。

当小$i$完成全部$n$个关卡后会自动结束游戏，进行结算。

结算时小$i$最多获得了多少金币？

输入

第一行一个正整数$T$表示数据组数。

对于每组数据，第一行输入两个正整数$n,H$，分别表示关卡数量和初始体力值。

接下来$n$行，每行输入$4$个正整数$A_i,B_i,C_i,D_i$。

$T\le 2000,1\le n,H,A_i,B_i,C_i,D_i\le 6000,\sum n+H\le 150000$,仅有$6$组数据满足$n,H>100$

输出

对于每组数据输出一行，表示小i最多能得到多少金币。

样例输入

2
2 8
2 2 1 2
1 4 3 3
4 9
3 1 3 2
2 2 2 2
4 3 3 1
2 4 2 1

样例输入

6
7

思路

从第一关到第n关, 不能跳过, 只能选择三种操作：

• 花费 $a_i$ 生命, 获得 $b_i$ 金币
• 花费 $c_i$ 生命, 获得 $d_i$ 金币
• 结束闯关

需要从三种决策中, 找到一种选择方案, 使得结束时得到的总金币最多。是一个分组背包问题, 我们只需要处理前两种操作就行。第三种操作通过在每次循环结束时更新 res 来实现。

状态定义：$f[i][j]$ 闯到第 $i$ 关后, 当前剩余 $j$ 生命的最大金币数 状态转移：

• 如果 $j\ge a_i$, $f[i][j]=f[i-1][j-a_i]+b_i$
• 如果 $j\ge c_i$, $f[i][j]=max\{f[i-1][j-c_i]+d_i,f[i][j]\}$ 因为不能跳过, 故第一条不能用 $f[i][j]=max\{f[i][j],f[i-1][j-a_i]+b_i\}$。

数据范围是1e5, 还需要用滚动数组优化一维, 把 $f[i]$ 替换为 $f[i\&1]$, 将 $f[i-1]$ 替换为 $f[i-1\&1]$ 即可。

注意限制条件为恰好为 $j$, 需要注意无法转移的状态, 初始化时除了 $f[0][0]=0$, 其余都初始化为-1, 并且在转移时也需要判断前一个状态是否存在, 即 $f[i-1]\ne -1$ 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
using namespace std;
const int N = 6e3 + 10;
int f[2][N];
int T;
int a[N], b[N], c[N], d[N];
 
 
int main()
{
 
    cin >> T;
    while (T--)
    {
        int n, H;
        cin >> n >> H;
        for (int i = 1; i <= n; i++)
            cin >> a[i] >> b[i] >> c[i] >> d[i];
        memset(f, -0x3f, sizeof f);
        f[0][0] = 0;
        int res = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= H; j++)
            {
                int v = -1;
                if (a[i] <= j && f[i - 1 & 1][j - a[i]] >= 0)
                    v = f[i - 1 & 1][j - a[i]] + b[i];
                if (c[i] <= j && f[i - 1 & 1][j - c[i]] >= 0)
                    v = max(f[i - 1 & 1][j - c[i]] + d[i], v);
                f[i & 1][j] = v;
                res = max(res, f[i & 1][j]);
            }
        }
 
        cout << res << endl;
    }
    return 0;
}