Editorial for Đèn hiệu đơn độc

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Xét riêng đóng góp của từng đèn

Một đoạn cảm biến chỉ được tính khi nó chứa đúng một đèn. Gắn đóng góp đó cho vị trí của đèn duy nhất nằm trong đoạn.

Gợi ý 2 - Chỉ cần biết hai đèn lân cận

Giả sử đèn đang xét ở vị trí b, đèn được chọn gần nhất bên trái ở a và bên phải ở c. Một cảm biến [l,r] chỉ chứa riêng đèn b khi a < l <= b <= r < c. Thêm hai vị trí lính canh 0 và N+1 ở hai đầu.

Lời giải đầy đủ

Hàm đóng góp

Với ba vị trí a < b < c, gọi gain(a,b,c) là tổng trọng số của các cảm biến thỏa a < l <= b <= r < c. Đây chính xác là các cảm biến chứa b nhưng không chứa đèn được chọn nào khác.

Ta tiền tính gain cho mọi bộ ba bằng cách duyệt M cảm biến. Với N <= 30, phần này chỉ mất O(MN^3).

Quy hoạch động

Gọi dp[t][a][b] là giá trị tốt nhất sau khi đã chọn t vị trí, hai vị trí cuối là a,b. Chi phí của các đèn đã chọn được trừ hết; phần thưởng của mọi đèn trừ b đã được chốt. Với lựa chọn đầu tiên b, khởi tạo dp[1][0][b] = -cost[b].

Khi thêm đèn c, ta chốt phần thưởng của b và trừ chi phí của c:

dp[t+1][b][c] = max(dp[t+1][b][c], dp[t][a][b] + gain(a,b,c) - cost[c]).

Sau khi chọn đủ K đèn, chốt đèn cuối cùng bằng vị trí lính canh N+1 và lấy kết quả lớn nhất.

Độ phức tạp

Tiền tính gain mất O(MN^3); DP mất O(KN^3). Bộ nhớ O(KN^2 + N^3).

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

const long long NEG = -(1LL << 60);

struct Sensor {
    int l, r;
    long long w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    vector<long long> cost(n + 1);
    for (int i = 1; i <= n; ++i) cin >> cost[i];

    vector<Sensor> sensors(m);
    for (auto& s : sensors) cin >> s.l >> s.r >> s.w;

    vector<vector<vector<long long>>> gain(
        n + 1, vector<vector<long long>>(n + 1, vector<long long>(n + 2, 0))
    );

    for (int a = 0; a <= n; ++a) {
        for (int b = a + 1; b <= n; ++b) {
            for (int c = b + 1; c <= n + 1; ++c) {
                for (const Sensor& s : sensors) {
                    if (a < s.l && s.l <= b && b <= s.r && s.r < c)
                        gain[a][b][c] += s.w;
                }
            }
        }
    }

    vector<vector<vector<long long>>> dp(
        k + 1, vector<vector<long long>>(n + 1, vector<long long>(n + 1, NEG))
    );

    for (int b = 1; b <= n; ++b)
        dp[1][0][b] = -cost[b];

    for (int t = 1; t < k; ++t) {
        for (int a = 0; a <= n; ++a) {
            for (int b = a + 1; b <= n; ++b) {
                if (dp[t][a][b] == NEG) continue;
                for (int c = b + 1; c <= n; ++c) {
                    dp[t + 1][b][c] = max(
                        dp[t + 1][b][c],
                        dp[t][a][b] + gain[a][b][c] - cost[c]
                    );
                }
            }
        }
    }

    long long answer = NEG;
    for (int a = 0; a <= n; ++a) {
        for (int b = a + 1; b <= n; ++b) {
            if (dp[k][a][b] != NEG)
                answer = max(answer, dp[k][a][b] + gain[a][b][n + 1]);
        }
    }

    cout << answer << endl;
    return 0;
}

Loading...