B - Level Up(01背包)

题目链接：https://codeforces.com/gym/102392/problem/B 题意：给定s1和s2，分别为level1和level2所需经验值；给定n个经验包，经验包只允许使用一次，第i个经验包在level1时使用时需要 t i t_i ti​的时间，可以涨 x i x_i xi​经验值；在level1时使用时需要 r i r_i ri​的时间，可以涨 y i y_i yi​的经验值。只有升完level1才能升level2，在level1溢出的经验值算到level2上。问升完2级所需要的最小时间。

题解：给定s1和s2，分别为level1和level2所需经验值；给定n个经验包，经验包只允许使用一次，第i个经验包在level1时使用时需要 t i t_i ti​的时间，可以涨 x i x_i xi​经验值；在level1时使用时需要 r i r_i ri​的时间，可以涨 y i y_i yi​的经验值。只有升完level1才能升level2，在level1溢出的经验值算到level2上。问升完2级所需要的最小时间。 题解：01背包，dp[i][j]表示当前用n个物品时，已经积累了i个总经验值，且j个level1的经验值时的最小时间，对于每个物品，他要么贡献level1的，要么贡献level2的，我们都考虑下即可。注意要对这些物品进行按 x i x_i xi​从小到大排序，原因是，如果不排序，有些情况我们会漏掉，如level1所需经验值为100，其对应最优取法是{30+30+30+90}，溢出的80做为level2的经验值，如果没排序，第一个选择的是90，那么我们取第二个30时便已经溢出，把溢出的20做为level2的经验值，这样就取不到我们的最优取法{30+30+30+90}了。代码实现来自队友pzz。

#include 
using namespace std;
#define MAXN 1501
#define LL long long
const LL inf=0x3f3f3f3f3f3f3f3f;
LL dp[MAXN][MAXN];
struct node{
    LL x,t,y,r;
    bool operator