自动搬运

查看原文

来自洛谷，原作者为

	jhdrgfj 拒绝精神胜利法！！1

搬运于2025-08-24 22:56:51，当前版本为作者最后更新于2024-04-06 11:05:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

解法

我们不妨称小 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！

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