Lợi nhuận tối đa từ bán rượu vang trong C++

Đề bài

Cho n chai rượu vang hàng ngang, mỗi chai có giá trị ban đầu P1...Pn. Mỗi năm bán 1 chai ở đầu hoặc cuối. Năm thứ Y, lợi nhuận chai i = Y × Pi. Tìm thứ tự bán (start/end) và lợi nhuận tối đa.

Ví dụ

Giá: {2, 4, 6, 2, 5} → Thứ tự: start end end start start → Lợi nhuận max = 64

Thuật toán Quy hoạch động

DP trạng thái: dp[begin][end] = lợi nhuận max từ đoạn [begin, end]. Năm hiện tại = n - (end - begin). Chọn bán đầu hoặc cuối, lấy max. Lưu hành động tối ưu trong sell[begin][end] để truy vết.

Ví dụ minh họa

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

int dp[N][N];
int sell[N][N];

int maxProfitUtil(int price[], int begin, int end, int n) {
    if (dp[begin][end] != -1) return dp[begin][end];
    int year = n - (end - begin);
    if (begin == end) return year * price[begin];
    
    int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n);
    int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n);
    int ans = max(x, y);
    dp[begin][end] = ans;
    sell[begin][end] = (x >= y) ? 0 : 1; // 0: start, 1: end
    return ans;
}

int maxProfit(int price[], int n) {
    memset(dp, -1, sizeof(dp));
    int ans = maxProfitUtil(price, 0, n - 1, n);
    int i = 0, j = n - 1;
    while (i <= j) {
        if (sell[i][j] == 0) { cout << "start "; i++; }
        else { cout << "end "; j--; }
    }
    cout << endl;
    return ans;
}

int main() {
    int price[] = {2, 4, 6, 2, 5};
    int n = sizeof(price) / sizeof(price[0]);
    int ans = maxProfit(price, n);
    cout << "Maximum profit = " << ans << endl;
    return 0;
}

Kết quả

start end end start start
Maximum profit = 64

Độ phức tạp: O(n²) thời gian và không gian. Top-down DP với memoization.