C++: Lợi nhuận tối đa xây nhà với giới hạn chiều cao

Bài toán: n vị trí, chiều cao tối đa h. Lợi nhuận vị trí i = height[i]². m giới hạn: đoạn [l,r] chiều cao tối đa x. Tối đa hóa tổng bình phương.

Giải pháp tham lam: Khởi tạo tất cả height[i] = h. Với mỗi giới hạn, cập nhật height[i] = min(height[i], x) cho i ∈ [l,r]. Cuối cùng tổng height[i]².

Code C++

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

int solve(int n, int h, vector<vector<int>> T) {
    vector<int> height(n, h);
    for (auto &r : T) {
        int l = r[0], rr = r[1], x = r[2];
        for (int i = l - 1; i < rr; i++)
            height[i] = min(height[i], x);
    }
    long long ans = 0;
    for (int v : height) ans += 1LL * v * v;
    return ans;
}

int main() {
    int n = 3, h = 3;
    vector<vector<int>> T = {{1,1,1}, {2,2,3}, {3,3,2}};
    cout << solve(n, h, T) << endl; // 1^2 + 3^2 + 2^2 = 14
    return 0;
}

Kết quả

14