题目背景
LSL最近喜欢上了抽卡活动,但是她作为非酋,运气非常的差,每次抽卡都只能无奈的看着那一些比他幸运值高的好友,有一天幸运女神告诉她,如果她能去消灭一些怪物,则她的幸运值可以提高。
题目描述
现在LSL拿出了x个体力药水,准备开始去消灭怪物了。
由于体力药水每个只能用一次,所以 LSL要谨慎的使用这些药。悲剧的是,用药量没达到最少打败该怪物所需的属性药药量,则打这个怪物必输。例如他用 2 个药去打怪物,怪物却表明 3 个药才能打过,那么相当于你输了并且这两个属性药浪费了。
现在有 n 个怪物,给定失败时可获得的经验、胜利时可获得的经验,打败怪物至少需要的药量。
要求求出最大经验s,输出 5s。
输入格式
第一行两个数,n 和 x。
后面 n 行每行三个数,分别表示失败时获得的经验losei,胜利时获得的经验 wini和打过要至少使用的药数量 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
提示
【数据范围】
- 对于 10% 的数据,保证 x=0。
- 对于 30% 的数据,保证 0≤n≤10,0≤x≤20。
- 对于 60% 的数据,保证 0≤n,x≤100, 10<;losei,wini≤100,0≤usei≤5。
- 对于 100% 的数据,保证 0≤n,x≤103,0<;losei≤wini≤106,0≤usei≤103。
我的代码 可能没用
#include<bits/stdc++.h>
using namespace std;
//dp[i]=max(dp[i],dp[i-use[i]]+win[i];
//dp[i]=dp[i]+lose[i];
int n,x;
int lose[1005],win[1005],use[1005];
int dp[1005];
int main()
{
cin>>n>>x;
for(int i=0;i<n;i++)
{
cin>>lose[i]>>win[i]>>use[i];
}
for(int i=0;i<n;i++)
{
for(int j=x;j>=use[i];j--)
{
dp[j]=max(dp[j]+lose[i],dp[j-use[i]]+win[i]);
}
for(int j=1;j<=n;j++)
{
dp[i]=dp[i]+lose[i];
}
}
cout<<dp[n]*5;
return 0;
}