网站地址跟网页地址区别,域名注册后 免费自建网站,舟山市建设局网站,网站开发技术说明5 倍经验日
题目背景
现在乐斗有活动了#xff01;每打一个人可以获得 5 倍经验#xff01;absi2011 却无奈的看着那一些比他等级高的好友#xff0c;想着能否把他们干掉。干掉能拿不少经验的。
题目描述
现在 absi2011 拿出了 x x x 个迷你装药物#xff08;嗑药打人…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 x0 x0。对于 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 10lose_i,win_i\le 100 10losei,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 0lose_i\le win_i\le 10^6 0losei≤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 授权题目
01背包问题选与不选
当我们药水够用的时候可以选择答应他或者故意不打赢他
当不够用时我们肯定打不赢但是就算没有药水我们一样继续往下打毕竟一直输也有经验拿
具体体现的是我们的 f [ i ] [ j ] f[ i ][ j ] f[i][j]一定要包含所有的情况不要以最终结尾要求作为考量而是要以整体过程作为考量
二维写法
#includeiostream
using namespace std;
const int N 1e3 10;
struct Node { //当然可以不用结构体int lose, win, use;
}a[N];long long f[N][N];
int n, x;int main() {cin n x;for (int i 1; i n; i) {cin a[i].lose a[i].win a[i].use;}for (int i 1; i n; i) {for (int j 0; j x; j) { //j一定要从0开始遍历不然丢情况推荐不明情况的时候就从0开始遍历if (j a[i].use)f[i][j] f[i-1][j] a[i].lose;if (j a[i].use)f[i][j] max(f[i - 1][j - a[i].use] a[i].win,f[i-1][j]a[i].lose);}}cout f[n][x]*5; //不要忘了5倍经验return 0;
}一维写法类比01背包即可
#includeiostream
using namespace std;
const int N 1e3 10;
struct Node {int lose, win, use;
}a[N];long long f[N];
int n, x;int main() {cin n x;for (int i 1; i n; i) {cin a[i].lose a[i].win a[i].use;}for (int i 1; i n; i) {for (int j x; j 0; j--) {if (j a[i].use)f[j] f[j] a[i].lose;if (j a[i].use)f[j] max(f[j - a[i].use] a[i].win , f[j] a[i].lose);}}cout f[x]*5;return 0;
}
