洛谷 1359. 5倍经验日
原题链接
简单
作者:
我是java同学
,
2023-02-14 19:24:47
,
所有人可见
,
阅读 191
dp 贪心
- 集合:从前
i
个好友中选,且总药量不超过j
,且经验最高的所有方案
- 状态计算:
- 药水不够
f[i - 1][j] + l[i]
- 一个药都不用,直接认输,保存药剂
贪心
- 药水够
f[i - 1][j - u] + w[i]
- 用药水
f[i - 1][j] + l[i]
- 不用药水
f[i - 1][j] + l[i]
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1010;
int n, m;
LL f[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
int l, w, u;
cin >> l >> w >> u;
for (int j = 0; j <= m; j ++ )
{
if (j >= u)
f[i][j] = max(f[i - 1][j] + l, f[i - 1][j - u] + w);
else
f[i][j] = max(f[i - 1][j] + l, f[i][j]);
}
}
printf("%lld\n", f[n][m] * 5);
return 0;
}