题目链接：https://www.luogu.com.cn/problem/P1802


题目背景

现在乐斗有活动了！每打一个人可以获得 5 倍经验！absi2011 却无奈的看着那一些比他等级高的好友，想着能否把他们干掉。干掉能拿不少经验的。

题目描述

现在 absi2011 拿出了 x 个迷你装药物（嗑药打人可耻…），准备开始与那些人打了。

由于迷你装药物每个只能用一次，所以 absi2011 要谨慎的使用这些药。悲剧的是，用药量没达到最少打败该人所需的属性药药量，则打这个人必输。例如他用 2 个药去打别人，别人却表明 3 个药才能打过，那么相当于你输了并且这两个属性药浪费了。

现在有 n 个好友，给定失败时可获得的经验、胜利时可获得的经验，打败他至少需要的药量。

要求求出最大经验 s，输出 5s。

输入格式

第一行两个数，n 和 x。

后面 n 行每行三个数，分别表示失败时获得的经验 \mathit{lose}_i，胜利时获得的经验 \mathit{win}_i 和打过要至少使用的药数量 \mathit{use}_i。

输出格式

一个整数，最多获得的经验的五倍。

说明/提示


【Hint】

五倍经验活动的时候，absi2011 总是吃体力药水而不是这种属性药。

【数据范围】

  • 对于 10\% 的数据，保证 x=0。
  • 对于 30\% 的数据，保证 0\le n\le 10，0\le x\le 20。
  • 对于 60\% 的数据，保证 0\le n,x\le 100， 10<lose_i,win_i\le 100，0\le use_i\le 5。
  • 对于 100\% 的数据，保证 0\le n,x\le 10^3，0<lose_i\le win_i\le 10^6，0\le use_i\le 10^3。

一道01背包问题的变形题，题目中在普通01背包中的 不选情况下添加一种 同样获取价值的操作。
拿着我写的注释来分析一下
//  价值 有两种    失败价值  和   成功价值
//  容量就是 拥有的药水   ，花费是所需要的药水    求  最大获取经验值
//  就是用不用药水的问题，如果用获取高经验，不用获取低经验
//   aij   表示   在使用药水范围为  j以内，枚举物品为 前i  个时的最优解
特别的，在描述状态转移方程时，需要考虑某一个好友是否添加了失败和成功。在这里我的处理方法是在描述状态转移方程时，每次从不包含改好友的情况下考虑，这样无论是成功还是失败，都保证只添加了一次。另外一个需要注意的地方就是数据范围，药水的数量可以是0，且药水是0时不一定一定失败，因为有些好友打败他不需要药水

完整代码： 


#include<bits/stdc++.h>
using namespace std;
long long dp[1010][1010],fail[1010],suc[1010],val[1010];
int main()
{
	//  价值 有两种    失败价值  和   成功价值
	//  容量就是 拥有的药水   ，花费是所需要的药水    求  最大获取经验值
	//  就是用不用药水的问题，如果用获取高经验，不用获取低经验
	//   aij   表示   在使用药水范围为  j以内，枚举物品为 前i  个时的最优解
	long long n,x; 
	cin>>n>>x;
	for(long long i=1;i<=n;i++)
	{
		cin>>fail[i]>>suc[i]>>val[i];
	} 
	for(long long i=1;i<=n;i++)
	{
		for(long long j=0;j<=x;j++)
		{
			if(j<val[i])
			{
				dp[i][j] = dp[i-1][j]+fail[i];
			}else
			{
				if(dp[i-1][j]+fail[i]<dp[i-1][j-val[i]]+suc[i])//使用药水 
				{
					dp[i][j] = dp[i-1][j-val[i]]+suc[i];
				}else								//不使用药水 
				{
					dp[i][j] = dp[i-1][j]+fail[i];
				}
			}
		}
	}
	cout<<5*dp[n][x]<<endl;
}