Reducing Dishes trong C++

Đầu bếp có n món, mỗi món có độ hài lòng satisfaction[i]. Món i nấu tại thời điểm t có hệ số like-time = t * satisfaction[i]. Có thể bỏ qua món. Tối đa hóa tổng like-time.

Ví dụ: [-1,-7,0,6,-7] → bỏ -7 (vị trí 2) và -7 (cuối) → -1*1 + 0*2 + 6*3 = 17.

Giải thuật (DP + Sắp xếp)

Sắp xếp satisfaction tăng dần. DP[i][time] = max sum từ món i..n-1 với thời gian bắt đầu = time. Chọn: bỏ món i, hoặc nấu món i (time * satisfaction[i] + DP[i+1][time+1]).

Ví dụ triển khai 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 skip = solve(idx + 1, time, v);
        int take = v[idx] * time + solve(idx + 1, time + 1, v);
        return dp[idx][time] = max(skip, take);
    }
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;
}

Đầu vào / Đầu ra

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