社区讨论
疑问
P1417烹调方案参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo2lgy7q
- 此快照首次捕获于
- 2023/10/23 15:46 2 年前
- 此快照最后确认于
- 2023/10/23 15:46 2 年前
这个题目的题面是不是有点问题,它没有说明最后的结果能不能为负数,理论上来说a-b*t是可能出现负数的,我考虑了负数第14个点还错了,下面被我注释掉的转移方程是考虑了负数的,没有注释的转移方程是没考虑负数的
CPP void solve() {
int t, num;
cin >> t >> num;
for (int i = 1; i <= num; i++) cin >> arr[i].a;
for (int i = 1; i <= num; i++) cin >> arr[i].b;
for (int i = 1; i <= num; i++) cin >> arr[i].c;
sort(arr + 1, arr + num + 1, cmp);
// for (int i = 0; i <= t; i++) { // 初始化为最小
// dp[i] = LLONG_MIN;
// }
for (int i = 1; i <= num; i++) { // 枚举每一个物品
for (ll j = t; j >= arr[i].c; j--) {
// dp[j] = max(dp[j], (dp[j - arr[i].c] == LLONG_MIN ? 0 : dp[j - arr[i].c]) + arr[i].a - arr[i].b * j);
dp[j] = max(dp[j], dp[j - arr[i].c] + arr[i].a - arr[i].b * j);
}
}
ll ans = LLONG_MIN;
for (int i = 0; i <= t; i++) {
ans = max(ans, dp[i]);
}
cout << ans << '\n';
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...