Bảng quảng cáo cao nhất trong C++

Cho tập thanh sắt, mỗi thanh có độ dài. Cần chọn hai tập con disjoint có tổng độ dài bằng nhau, tối đa hóa tổng đó (chiều cao bảng quảng cáo). Trả về 0 nếu không thể.

Ví dụ: [1,2,2,3,3,3,4] → 9 (tập [1,2,2,4] và [3,3,3]).

Giải thuật

1. DP: dp[i][j] = tổng lớn nhất của tập "cao hơn" khi xem xét i thanh đầu tiên, chênh lệch giữa hai tập là j - 5000 (dịch chỉ số âm).
2. Khởi tạo dp[0][5000] = 0.
3. Với mỗi thanh x = rods[i], cập nhật dp[i+1][j] từ dp[i]:
   • Thêm x vào tập cao hơn: dp[i+1][j] = max(dp[i+1][j], dp[i][j-x] + x) nếu j-x ≥ 0.
   • Thêm x vào tập thấp hơn: dp[i+1][j] = max(dp[i+1][j], dp[i][j+x]) nếu j+x ≤ N.
   • Không dùng thanh: dp[i+1][j] = max(dp[i+1][j], dp[i][j]).
4. Kết quả dp[n][5000].

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int tallestBillboard(vector<int>& rods){
        int n = rods.size();
        int N = 2 * 5000;
        vector<vector<int> > dp(n + 1, vector<int>(N + 1, -1));
        dp[0][5000] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= N; j++) {
                int x = rods[i];
                if (j - x >= 0 && dp[i][j - x] != -1)
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j-x] + x);
                if (j + x <= N && dp[i][j + x] != -1)
                    dp[i+1][j] = max(dp[i+1][j], dp[i][j+x]);
                if (dp[i][j] != -1)
                    dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
            }
        }
        return dp[n][5000];
    }
};
int main(){
    Solution ob;
    vector<int> v = {1,2,2,3,3,3,4};
    cout << (ob.tallestBillboard(v));
}

Đầu vào

{1,2,2,3,3,3,4}

Đầu ra

9