题解：P10316[SHUPC 2024]为美好的世界献上爆焰!

美好的一天从写题解开始。

感谢 @jhdrgfj 的思路

思路

很显然，设 $f_{i,j}$ 为在第 $i$ 天造成 $j$ 点伤害。

但是，每一天都是一个 01 背包，任意两天的魔力值都是互不影响的，所以考虑每一天一次 dp。
设 $f_i$ 为将魔力值提高到 $i$ 的最小花费（当天），就是求 01 背包。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAX 1145141818810ll
//照楼上
int n, x, s, m, f1[5010], f2[5010], w[5010], v[5010];
signed main()
{
	cin >> n >> x >> s >> m;
	for(int i = 1; i <= x; i++)
		f1[i] = MAX;
	for(int i = 1; i <= n; i++)
	{
		for(int j = m + 1; j <= s; j++)//f2需要每次清理
			f2[j] = MAX;
		int N, sum = 0;
		cin >> N;
		for(int j = 1; j <= N; j++)
			cin >> v[j];
		for(int j = 1; j <= N; j++)
			cin >> w[j], sum += w[j];
		sum = min(sum + m, s);
		/*更新f2*/
		for(int j = 1; j <= N; j++)
			for(int k = sum; k >= w[j]; k--)
				f2[k] = min(f2[k], f2[k - w[j]] + v[j]);
		/*更新f1*/
		for(int j = x; j >= 0; j--)
			for(int k = m; k <= sum; k++)
				f1[j] = min(f1[j], f1[max(j - k, 0ll)] + f2[k]);//max(j - k, 0ll)防止可能出现负数
	}
	cout << (f1[x] == MAX ? -1 : f1[x]);
	return 0;
}