Minecraft123 @ 2023-05-14 12:45:01
这个题目的题面是不是有点问题,它没有说明最后的结果能不能为负数,理论上来说a-b*t是可能出现负数的,我考虑了负数第14个点还错了,下面被我注释掉的转移方程是考虑了负数的,没有注释的转移方程是没考虑负数的
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';
}
by Minecraft123 @ 2023-05-14 12:46:15
@Minecraft123 我的数据都是ll的所以应该不是溢出的问题
by ZBH_123 @ 2023-08-02 16:11:27
记得开 long long
。
by Running_a_way @ 2024-01-30 20:40:25
@Minecraft123 什么菜都不做就已经是