Reducing Dishes: เพิ่มประสิทธิภาพ Like-time Coefficient ใน C++

ปัญหา

เชฟมีจานอาหาร n จาน แต่ละจานมีระดับความพึงพอใจ satisfaction[i] การทำจานหนึ่งใช้เวลา 1 หน่วย Like-time coefficient ของจานที่ทำเป็นลำดับที่ t คือ t × satisfaction[i] สามารถทำจานในลำดับใดก็ได้ และ สามารถทิ้งจานบางจานได้ หาผลรวม Like-time coefficient สูงสุด

ตัวอย่าง: [-1,-7,0,6,-7] → ทิ้ง -7 ตัวที่ 2 และตัวสุดท้าย → ลำดับ: -1, 0, 6 → -1×1 + 0×2 + 6×3 = 17

ข้อสังเกตสำคัญ

1. เรียงลำดับ satisfaction จากน้อยไปมาก เพราะค่าติดลบควรทำก่อน (คูณ t น้อย) ค่าบวกควรทำทีหลัง (คูณ t มาก)
2. ปัญหากลายเป็น: เลือก Subsequence จากอาร์เรย์ที่เรียงแล้ว ให้ Σ (index_in_subsequence × value) สูงสุด

แนวคิด: DP + Memoization

State

dp[idx][time] = คะแนนสูงสุดจากจาน idx..n-1 โดยจานถัดไปจะเป็นลำดับที่ time

Recurrence

dp[idx][time] = max(
    solve(idx + 1, time),                    // ข้ามจานนี้
    satisfaction[idx] * time + solve(idx + 1, time + 1)  // ทำจานนี้
)

Base Case

idx == n → return 0

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int dp[505][505];
    
    int solve(int idx, int time, vector<int>& v) {
        if (idx == v.size()) return 0;
        if (dp[idx][time] != -1) return dp[idx][time];
        
        int ret = INT_MIN;
        // ตัวเลือก 1: ข้ามจานนี้
        // ตัวเลือก 2: ทำจานนี้ (ได้ v[idx] * time) แล้ว time+1
        ret = max(solve(idx + 1, time, v), 
                  v[idx] * time + solve(idx + 1, time + 1, v));
        
        return dp[idx][time] = ret;
    }
    
public:
    int maxSatisfaction(vector<int>& v) {
        memset(dp, -1, sizeof(dp));
        sort(v.begin(), v.end());  // สำคัญ: เรียงน้อยไปมาก
        return solve(0, 1, v);
    }
};

int main() {
    Solution ob;
    vector<int> v = {-1, -7, 0, 6, -7};
    cout << ob.maxSatisfaction(v);  // 17
    return 0;
}

วิธี Greedy (Simpler, O(n log n))

หลังเรียงแล้ว เริ่มจากท้าย (ค่าบวกมากสุด) สะสมผลรวม ย้อนกลับมาหน้าจนกว่าผลรวมสะสมจะติดลบ:

int maxSatisfaction(vector<int>& v) {
    sort(v.begin(), v.end());
    int suffix_sum = 0, total = 0;
    for (int i = v.size() - 1; i >= 0; i--) {
        suffix_sum += v[i];
        if (suffix_sum < 0) break;
        total += suffix_sum;
    }
    return total;
}

เหตุผล: เพิ่มจานหน้าสุด (ค่าน้อยลง) จะเพิ่ม suffix_sum เข้า total ทุกครั้ง ถ้า suffix_sum < 0 การเพิ่มจะลด total

ความซับซ้อน

Input / Output

Input:  {-1,-7,0,6,-7}
Output: 17