洛谷 1417. 烹调方案
原题链接
中等
作者:
我是java同学
,
2023-02-06 17:46:39
,
所有人可见
,
阅读 218
01背包 dp
- 物品的价值会随时间的变化而变化,每个时间对应一个价值(==不同物品),而只能选一次,自然不能用
01
背包。(不同顺序选取会影响答案,而01
背包不会)
-
- 用结构题匿名函数排序
- 注意
f[N]
的数据范围,abc
卡longlong
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 55;
int n, m;
LL f[100010];
struct st {
LL a, b, c;
}x[N];
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) cin >> x[i].a;
for (int i = 1; i <= n; i ++ ) cin >> x[i].b;
for (int i = 1; i <= n; i ++ ) cin >> x[i].c;
sort(x + 1, x + n + 1, [&](st A, st B) {
return A.b * B.c > B.b * A.c;
});
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= x[i].c; j -- )
f[j] = max(f[j], f[j - x[i].c] + x[i].a - j * x[i].b);
LL res = 0;
for (int i = 1; i <= m; i ++ ) res = max(res, f[i]);
cout << res << endl;
return 0;
}
这个题解应该不是这题的吧
是洛谷的,我改改