社区讨论

疑问

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 条回复,欢迎继续交流。

正在加载回复...