疑问

P1417 烹调方案

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 什么菜都不做就已经是 0 了。


|