[数据结构与算法]2021ccpc河南省赛《闯关游戏》dp

http://acm.zzuli.edu.cn/problem.php?id=2829

#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int dp[2][N];
int n, m;
void solve()
{
	cin >> n >> m;
	for (int i = 0; i <= m; i++)
		dp[0][i] = -0x3f3f3f3f;
	dp[0][0] = 0;
	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		for (int j = 0; j <= m; j++)
		{
			int k = -0x3f3f3f3f;
			if (j >= a && dp[i - 1 & 1][j - a] >= 0)k = dp[i - 1 & 1][j - a] + b;
			if (j >= c && dp[i - 1 & 1][j - c] >= 0)k = max(k, dp[i - 1 & 1][j - c] + d);
			dp[i & 1][j] = k;
			res = max(res, k);
		}
	}
	cout << res << endl;
}
int main()
{
	int _;
	cin >> _;
	while (_--)solve();
}