#include<bits/stdc++.h>
using namespace std;
long long dp[1005][1005];
long long lose[1000005];
long long win[1000005];
long long en[1000005];
int main()
{
long long n,x;
cin >> n >> x;
for (int i = 1;i <= n;i++){
cin >> lose[i] >> win[i] >> en[i];
}
for (int i = 1;i <= n;i++){
for (int j = 0;j <= x;j++){
if (j >= en[i]){
dp[i][j] = max(dp[i-1][j-en[i]]+win[i] , dp[i-1][j]+lose[i]);
}
else {
dp[i][j] = dp[i-1][j] + lose[i];
}
}
}
cout << dp[n][x] * 5;
return 0;
}
5 倍经验日
题目背景
现在乐斗有活动了!每打一个人可以获得 5 倍经验!absi2011 却无奈的看着那一些比他等级高的好友,想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 x x x 个迷你装药物(嗑药打人可耻…),准备开始与那些人打了。
由于迷你装药物每个只能用一次,所以 absi2011 要谨慎的使用这些药。悲剧的是,用药量没达到最少打败该人所需的属性药药量,则打这个人必输。例如他用 2 2 2 个药去打别人,别人却表明 3 3 3 个药才能打过,那么相当于你输了并且这两个属性药浪费了。
现在有 n n n 个好友,给定失败时可获得的经验、胜利时可获得的经验,打败他至少需要的药量。
要求求出最大经验 s s s,输出 5 s 5s 5s。
输入格式
第一行两个数, n n n 和 x x x。
后面 n n n 行每行三个数,分别表示失败时获得的经验 l o s e i \mathit{lose}_i losei,胜利时获得的经验 w i n i \mathit{win}_i wini 和打过要至少使用的药数量 u s e i \mathit{use}_i usei。
输出格式
一个整数,最多获得的经验的五倍。
样例 #1
样例输入 #1
6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2
样例输出 #1
1060
提示
【Hint】
五倍经验活动的时候,absi2011 总是吃体力药水而不是这种属性药。
【数据范围】
- 对于 10 % 10\% 10% 的数据,保证 x = 0 x=0 x=0。
- 对于 30 % 30\% 30% 的数据,保证 0 ≤ n ≤ 10 0\le n\le 10 0≤n≤10, 0 ≤ x ≤ 20 0\le x\le 20 0≤x≤20。
- 对于 60 % 60\% 60% 的数据,保证 0 ≤ n , x ≤ 100 0\le n,x\le 100 0≤n,x≤100, 10 < l o s e i , w i n i ≤ 100 10<lose_i,win_i\le 100 10<losei,wini≤100, 0 ≤ u s e i ≤ 5 0\le use_i\le 5 0≤usei≤5。
- 对于 100 % 100\% 100% 的数据,保证 0 ≤ n , x ≤ 1 0 3 0\le n,x\le 10^3 0≤n,x≤103, 0 < l o s e i ≤ w i n i ≤ 1 0 6 0<lose_i\le win_i\le 10^6 0<losei≤wini≤106, 0 ≤ u s e i ≤ 1 0 3 0\le use_i\le 10^3 0≤usei≤103。
【题目来源】
fight.pet.qq.com
absi2011 授权题目