Nhận xét

Robot có thể xây hoàn chỉnh những bước tường ứng với dãy ~b_1, b_2,..., b_n~ nếu dãy ~b~ thỏa mãn ít nhất một trong các điều kiện sau:

• ~b~ là dãy không giảm.
• ~b~ là dãy không tăng.
• Tồn tại 1 giá trị ~i~ sao cho dãy ~b_1, b_2,..., b_i~ là dãy không giảm và dãy ~b_{i + 1}, b_{i + 2}, ..., b_n~ là dãy không tăng.

Phát biểu lại bài toán: cho dãy ~a_1, a_2,..., a_n~ cần tìm dãy ~b_1, b_2,..., b_n~ thỏa mãn ít nhất một trong ba điều kiện nêu trên sao cho giá trị ~T = \sum\limits_{i = 1}^n|S(a_i) - S(b_i)|~ nhỏ nhất có thể, trong đó ~S(x) = x*(x + 1)~.

Gọi ~pre_i~ là kết quả bài toán nếu dãy ~a~ chỉ bao gồm ~i~ phần tử đầu (các phần tử giữ nguyên thứ tự) và dãy ~b~ là dãy không giảm (quy ước ~pre_0 = 0~).

Gọi ~suf_i~ là kết quả bài toán nếu dãy ~a~ chỉ bao gồm ~i~ phần tử cuối (các phần tử giữ nguyên thứ tự) và dãy ~b~ là dãy không tăng (quy ước ~suf_0 = 0~).

Ta có thể tìm được hai mảng ~pre, suf~ bằng kĩ thuật Slope Trick (*).

Kết quả bài toán là giá trị ~pre_i+suf_{n - i}~ nhỏ nhất thỏa ~0 \leq i \leq n~.

(*): Tham khảo kĩ thuật Slope Trick tại đây.

Để tìm được mảng ~pre~ trong bài này, ta có thể dùng thuật toán quy hoạch động tương tự với phần "Thuật toán QHĐ cơ sở" ở link bên trên.

Về phần quan sát đồ thị hàm QHĐ, ta coi "độ dốc" tại điểm ~j~ là ~\frac{F_i(j + 1) - F_i(j)}{2 * (j + 1)}~. Phần còn lại có tính chất và cách giải quyết tương tự như bài tập ví dụ.

Tham khảo đoạn code tìm mảng ~pre~:

Code mẫu

long long S(long long x) {return x * (x + 1);}

void solve(int n, long long a[], long long pre[]) {
    long long s = 0;
    priority_queue<long long> h;
    for (int i = 1; i <= n; i++) {
        h.push(a[i]);
        if (!h.empty() && a[i] < h.top()) {
            s += S(h.top()) - S(a[i]);
            h.pop();
            h.push(a[i]);
        }
        pre[i] = s;
    }
}