โปรแกรม C++ หากำไรสูงสุดจากการขายรถยนต์สีแดงและสีน้ำเงิน

บริษัทรถยนต์ต้องขาย p คันสีแดง และ q คันสีน้ำเงิน มีสต็อก: a คันสีแดง, b คันสีน้ำเงิน, c คันไม่มีสี (ทาสีได้ทั้ง 2 สี) ราคาในอาร์เรย์ A, B, C ตามลำดับ ต้องการกำไรสูงสุด

ตัวอย่าง: p=3,q=3,a=3,b=3,c=2, A={150000,200000,200000}, B={150000,120000,180000}, C={210000,160000,150000} ผลลัพธ์: 1100000

ขั้นตอนการแก้ปัญหา (Greedy + Prefix Sum)

1. เรียง A, B, C ใหญ่ไปเล็ก
2. สร้างอาร์เรย์ dp เริ่มด้วย 0 แล้วใส่ p ค่าแรกของ A และ q ค่าแรกของ B
3. เรียง dp ใหญ่ไปเล็ก คำนวณ prefix sum
4. ลองนำรถไม่มีสี i = 1 ถึง min(c, p+q) คันมาใช้ (ค่าสูงสุด i คันแรกของ C) แทนที่ค่าต่ำสุดใน dp คำนวณผลรวมใหม่ หาค่าสูงสุด

ตัวอย่างโค้ด C++

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

int solve(int p, int q, int a, int b, int c,
          vector<int> A, vector<int> B, vector<int> C) {
    vector<int> dp(1, 0);
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());
    sort(C.rbegin(), C.rend());
    for (int i = 0; i < p; ++i) dp.push_back(A[i]);
    for (int i = 0; i < q; ++i) dp.push_back(B[i]);
    sort(dp.begin(), dp.end());
    reverse(dp.begin() + 1, dp.end());
    for (int i = 1; i < (int)dp.size(); ++i) dp[i] += dp[i-1];
    int tmp = 0, res = dp.back();
    for (int i = 1; i <= min(c, p + q); ++i) {
        tmp += C[i-1];
        res = max(res, dp[p + q - i] + tmp);
    }
    return res;
}

int main() {
    int p = 3, q = 3, a = 3, b = 3, c = 2;
    vector<int> A = {150000, 200000, 200000};
    vector<int> B = {150000, 120000, 180000};
    vector<int> C = {210000, 160000, 150000};
    cout << solve(p, q, a, b, c, A, B, C);
    return 0;
}

อินพุต / เอาต์พุต

Input: 3, 3, 3, 3, 2, {150000,200000,200000}, {150000,120000,180000}, {210000,160000,150000}

Output: 1100000