25.3.5刷题

https://www.luogu.com.cn/problem/P1802

P1802 5倍经验日

题解

01背包的变形，不选择也会有增加值

拥有药水数量就是背包容量，每种物品有两种价值，注意状态转移方程，还有不选择物品时，也会增加价值

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, m;
long long dp[N];
int lose[N], win[N], use[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;//处理输入
	for (int i = 1; i <= n; i++) cin >> lose[i] >> win[i] >> use[i];

	for (int i = 1; i <= n; i++)//01背包
	{
		for (int j = m; j >= use[i]; j--)
		{
			dp[j] = max(dp[j] + lose[i], dp[j - use[i]] + win[i]);
		}
		for (int j = use[i] - 1; j >= 0; j--)//药水数量不够，输了也会加经验，所以，小于药水需要量的情况都要加lose[i]
		{
			dp[j] += lose[i];
		}
	}

	cout << 5 * dp[m];//输出，答案可能爆int，所以用long long

	return 0;
}