为美好的世界献上爆焰！

· · 题解

昨晚刚把素晴第十五卷看完，准备看爆炎最后一卷。灌水时看到这个题很激动。

解法

我们不妨称小 A 为和真，小 B 为惠惠。

一个很显然的想法是，设 f_{i,j} 为第 i 天对魔王城造成 j 点伤害时和真所需的最小代价，则最终答案为 f_{n,x}。

但是我们需要考虑到魔晶石对惠惠魔力造成的影响，因为每天魔晶石与魔力都是独立的，所以我们考虑对每一天单独 dp。考虑设 g_i 为当天将惠惠的魔力补充至 i 时和真所需的最小代价，那么显然有 g_i=0 \ (0\le i \le m)。

我们可以将每个魔晶石的价格看成体积，魔力看成价值。求 g_i 便转化成了一个 01 背包问题，但是做 01 背包时价值如果枚举到惠惠的魔力上限会变成 O(nM\sum num)，无法接受。注意到 \sum h\le5000，故价值只要枚举到 \min(\sum h_i + m,M) 就行了。

现在我们求出了 g，考虑如何求出 f_i。我们枚举 j，再枚举惠惠今天的魔力。也就是 f_{i,j}=\min\{f_{i,j-k}+g_k\} \ (m \le k \le \sum h_i)。

然后本题就做完了。

代码

#include<bits/stdc++.h>
#define Explosion 1145141919810ll
#define int long long
using namespace std;
int dp1[5005],dp2[5005],n,x,s,m,w[5005],v[5005];
//dp1 对应 f，dp2 对应 g
//dp1 用了滚动数组优化
signed main()
{
    cin>>n>>x>>s>>m;
    for (int i=1;i<=x;i++){
        dp1[i]=Explosion;
    }
  //以下是上述的转移
    for (int i=1;i<=n;i++){
        int u,konosuba=0;
        cin>>u;
        for (int j=1;j<=u;j++){
            cin>>v[j];
        }
        for (int j=1;j<=u;j++){
            cin>>w[j];
            konosuba+=w[j];
        }
        for (int j=m+1;j<=s;j++){
            dp2[j]=Explosion;
        }
        konosuba=min(konosuba+m,s);
        for (int j=1;j<=u;j++){
            for (int k=konosuba;k>=w[j];k--){
                dp2[k]=min(dp2[k],dp2[k-w[j]]+v[j]);
            }
        }
        for (int j=x;j>=0;j--){
            for (int k=m;k<=konosuba;k++){
                dp1[j]=min(dp1[j],dp1[max(j-k,0ll)]+dp2[k]);
              //max(j-k,0ll) 防止出现负数 
            }
        }
    }
    cout<<(dp1[x]==Explosion?-1:dp1[x]);
}
// Explosion！

说句题外话，素晴第三季四天后就播出了，真好。希望有生之年能看到素晴第四季和爆炎第二季。