题解：P11069 「QMSOI R1」生熏鱼

ylch · 2024-11-09 19:43:31 · 题解

Description

抽象题意：有 n 种、k 个物品，和一个体积为 m 的背包，每个物品的收益为 a_i，体积为 b_i。

你只能依次选择这 k 个物品，且无法跳过不选。

为了获得更多的收益，有一种超能力，可以从 n 种物品中选择若干种物品，并在这些种类的物品第一次出现时放弃选择该种物品。

求最后能获得的最大收益。

Analysis

这道题的正解是 01 背包。（我个人认为出题人的解法复杂度并不稳定，可能只是因为随机数据卡过去了）

具体地，首先用前缀和的思想统计所有的经验和损失，然后顺序遍历 k 次攻击，假设当前是第 i 次攻击，同时当前血量 m<0，那么，我们就要想办法从前面防御一些攻击，使得血量刚好可以回正（即减少 1-m 的伤害），同时又不损失过多的经验。

那么，我们可以在每种物品第一次出现时，做一次 01 背包，得到要回一定血量所需的最小代价。

然后，对于血量 m<0 的情况，通过在总经验上减去 dp[1-m] 的经验，来维持血量，同时统计经验最大值

注意两个细节：

我们减去的 dp[1-m] 的经验要取后缀最小值，因为会出现回血多、经验值损失反而少的情况（题目并不保证失去血量越大，经验值越多）。
我们“减去经验”“回血”等都是为了统计答案所使用，不能改变正常的血量、前缀和，因为这只是我们做出的“假设”，不对正常状况做出影响。

也可以这么理解：这里的经验损失、回血一定会在之后的循环中被其他 dp 状态所包含（因为越往后累计伤害越大、被迫损失经验越多）。

这样时间复杂度为 O(k + n^2 \times C)，因为每种攻击只在第一次出现时跑 dp，所以背包 dp 的循环只会执行 n 次。同时，题目的血量最大值 C \le 10^5+5，数组的空间不会超限。

Summary

这道题和普通 01 背包的区别是：这道题是随着 k 次伤害的遍历、是否有某种攻击的首次出现来进行 dp，而不是传统的先对全部情况 dp 预处理，再在处理询问时直接输出。

这道题可以更好地加深我们对传统背包 dp 的理解。

Code

附详细注释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 30, maxk = 2e7 + 5;
const int M = 1e9, C = 1e5 + 5;

int n, m, k, s;
int a[maxn], b[maxn], c[maxk];
ll dp[C * maxn], suf[C * maxn]; // dp[j]表示（前i种攻击）剩余血量为j时，得到的最小经验值；suf是后缀最小值
bool vis[maxn]; // vis[i]表示第i种攻击是否出现过

void solve()
{
    cin>>n>>m>>k>>s;
    mt19937 rand(s);
    for(int i=1;i<=n;i++)  a[i]=rand()%M+1,b[i]=rand()%C+1;
    for(int i=1;i<=k;i++)  c[i]=rand()%n+1;

    // 初始化为较大值（加法不爆）
    memset(dp, 0x3f, sizeof dp);
    memset(suf, 0x3f, sizeof suf);
    dp[0] = 0;

    ll sum = 0, maxn = 0; // s统计经验前缀和、maxn统计能获得的最大经验
    for(int i = 1; i <= k; i ++){
        if(!vis[c[i]]){ // 如果这是第c[i]种攻击第一次出现
            vis[c[i]] = 1;
            // 背包dp
            for(int j = C * n; j >= b[c[i]]; j --){ // 注意滚动数组要倒着遍历，避免提前计算
                dp[j] = min(dp[j], dp[j - b[c[i]]] + a[c[i]]);
            }
            // 统计后缀最小值
            for(int j = C * n; j >= 0; j --){
                suf[j] = min(suf[j + 1], dp[j]);
            }
        }

        sum += a[c[i]];
        if(m <= 0){
            // 防止越界 和 不存在的状态被计入答案
            if(1 - m <= C * n && suf[1 - m] != LLONG_MAX){
                maxn = max(maxn, sum - suf[1 - m]);
                // 这里不用把sum减去经验值，因为回血只是为统计做出的假设，不影响正常进程
            }
            else break; // 否则说明救不回来了，退出循环即可
        }
        else{ // 注意这个else非常关键，因为如果进了上一个if，当前统计上的s应该是减去一部分经验值的，而不是原值
            maxn = max(maxn, sum);
        }
        m -= b[c[i]]; // 和sum同理，这里不用把m回正
    }

    cout << maxn << '\n';
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

End

管理员大大辛苦啦~

谢谢大家！

题解：P11069 「QMSOI R1」 生熏鱼

Description

Analysis

Summary

Code

End

题解：P11069 「QMSOI R1」生熏鱼