Hiểu bài toán

Bài toán yêu cầu tìm độ dài lớn nhất của đường gấp khúc phía trên khi đặt liên tiếp n hình chữ nhật có kích thước (ai, bi) dọc theo trục Ox. Mỗi hình chữ nhật có thể được xoay 90 độ (tức là sử dụng một cạnh làm chiều rộng và cạnh còn lại làm chiều cao). Điều kiện quan trọng là ai <= bi, nghĩa là một cạnh luôn ngắn hơn hoặc bằng cạnh kia.

Đường gấp khúc được hình thành bởi các đoạn thẳng nằm ngang và dọc. Dựa vào hình minh họa và điều kiện ai <= bi, ta thấy:

• Nếu không xoay: Chiều rộng là ai, chiều cao là bi. Đường gấp khúc sẽ có một đoạn ngang bằng a_i (chiều rộng) và một đoạn dọc (chiê'u cao).
• Nếu xoay: Chiều rộng là bi, chiều cao là ai. Đường gấp khúc sẽ có một đoạn ngang bằng b_i và một đoạn dọc.

Vì ai <= bi, để tối ưu độ dài đường gấp khúc, ta luôn muốn các đoạn ngang (chiều rộng) là số lớn nhất có thể. Tuy nhiên, độ dài đường gấp khúc không chỉ phụ thuộc vào chiều rộng của từng hình mà còn phụ thuộc vào sự chênh lệch chiều cao giữa các hình liên tiếp (độ dốc).

Mục tiêu: Tìm cách chọn chiều rộng (ai hoặc bi) cho mỗi hình sao cho tổng độ dài đường gấp khúc là lớn nhất.

Các cách tiếp cận

Cách Quy hoạch động cơ bản (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;cin>>n;
    vector<int> a(n+1);
    vector<int> b(n+1);
    for (int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }
    // dp[i][0]: độ dài lớn nhất đến hình thứ i khi hình i không xoay (chiều rộng a[i])
    // dp[i][1]: độ dài lớn nhất đến hình thứ i khi hình i xoay (chiều rộng b[i])
    vector<vector<int> > dp(n+1,vector<int>(n+1,0));
    dp[1][0]=a[1];
    dp[1][1]=b[1];
    for (int i=2;i<=n;i++){
        // Tính dp[i][0]: hình i không xoay
        // Nếu hình trước kia không xoay: cộng a[i] và cộng độ chênh lệch giữa b[i] và b[i-1]
        // Nếu hình trước kia xoay: cộng a[i] và cộng độ chênh lệch giữa b[i] và a[i-1]
        dp[i][0]=max(
            dp[i-1][0] + a[i] + abs(b[i]-b[i-1]),
            dp[i-1][1] + a[i] + abs(b[i]-a[i-1])
        );
        // Tính dp[i][1]: hình i xoay
        // Nếu hình trước kia không xoay: cộng b[i] và cộng độ chênh lệch giữa a[i] và b[i-1]
        // Nếu hình trước kia xoay: cộng b[i] và cộng độ chênh lệch giữa a[i] và a[i-1]
        dp[i][1]=max(
            dp[i-1][0] + b[i] + abs(a[i]-b[i-1]),
            dp[i-1][1] + b[i] + abs(a[i]-a[i-1])
        );
    }
    cout<<max(dp[n][0],dp[n][1]);
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa:

• dp[i][0]: Độ dài đường gấp khúc lớn nhất khi xét đến hình thứ i và hình thứ i được đặt với chiều rộng là a[i].
• dp[i][1]: Độ dài đường gấp khúc lớn nhất khi xét đến hình thứ i và hình thứ i được đặt với chiều rộng là b[i].

Công thức chuyển trạng thái: Để tính dp[i][0], ta xem xét hai trường hợp của hình trước đó (i-1):

1. Hình i-1 không xoay (chiều rộng a[i-1], chiều cao b[i-1]): Độ dài mới = dp[i-1][0] + a[i] + abs(b[i] - b[i-1]). Đoạn a[i] là chiều rộng hiện tại, abs(b[i] - b[i-1]) là độ chênh lệch chiều cao tạo ra đoạn dọc.
2. Hình i-1 xoay (chiều rộng b[i-1], chiều cao a[i-1]): Độ dài mới = dp[i-1][1] + a[i] + abs(b[i] - a[i-1]). Ta lấy giá trị lớn nhất trong hai trường hợp này.

Tương tự cho dp[i][1] với chiều rộng là b[i].

Độ phức tạp thời gian là O(N) do duyệt qua từng hình một lần. Độ phức tạp không gian là O(N) nếu lưu toàn bộ bảng, nhưng có thể tối ưu xuống O(1) bằng cách chỉ lưu 2 giá trị trước đó.

Cách Quy hoạch động tối ưu không gian (Space Optimized DP)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

    int n;
    cin >> n;
    vector<pair<long long, long long>> rects(n);
    for (int i = 0; i < n; ++i) {
        cin >> rects[i].first >> rects[i].second;
    }

    // dp0: độ dài lớn nhất khi hình trước đó có chiều rộng là a (không xoay)
    // dp1: độ dài lớn nhất khi hình trước đó có chiều rộng là b (xoay)
    long long dp0 = rects[0].first;
    long long dp1 = rects[0].second;

    // Lưu chiều cao của hình trước đó
    long long prev_h_a = rects[0].second; // Nếu không xoay, chiều cao là b
    long long prev_h_b = rects[0].first;  // Nếu xoay, chiều cao là a

    for (int i = 1; i < n; ++i) {
        long long a = rects[i].first;
        long long b = rects[i].second;

        // Tính giá trị mới cho hình hiện tại
        // Nếu hình hiện tại không xoay (chiều rộng a): 
        //   Chuyển từ dp0 (hình trước không xoay): dp0 + a + |b - prev_h_a|
        //   Chuyển từ dp1 (hình trước xoay):     dp1 + a + |b - prev_h_b|
        long long new_dp0 = max(dp0 + a + abs(b - prev_h_a), dp1 + a + abs(b - prev_h_b));

        // Nếu hình hiện tại xoay (chiều rộng b):
        //   Chuyển từ dp0: dp0 + b + |a - prev_h_a|
        //   Chuyển từ dp1: dp1 + b + |a - prev_h_b|
        long long new_dp1 = max(dp0 + b + abs(a - prev_h_a), dp1 + b + abs(a - prev_h_b));

        // Cập nhật biến lưu trạng thái
        dp0 = new_dp0;
        dp1 = new_dp1;
        prev_h_a = b; // Cập nhật chiều cao mới nếu không xoay
        prev_h_b = a; // Cập nhật chiều cao mới nếu xoay
    }

    cout << max(dp0, dp1) << endl;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là phiên bản cải tiến của phương pháp quy hoạch động cơ bản. Thay vì tạo một mảng 2 chiều lớn để lưu tất cả các giá trị dp, ta chỉ cần lưu hai giá trị của bước trước đó (dp0 và dp1) và hai chiều cao tương ứng.

Logic tính toán tương tự hoàn toàn:

• new_dp0 (trạng thái hiện tại, không xoay) được tính dựa trên dp0 và dp1 của bước trước.
• new_dp1 (trạng thái hiện tại, xoay) được tính dựa trên dp0 và dp1 của bước trước. Sau khi tính xong, ta cập nhật dp0, dp1 và các chiều cao lưu tạm cho bước lặp tiếp theo.

Phương pháp này hiệu quả hơn về mặt bộ nhớ, phù hợp với các bài toán có giới hạn bộ nhớ nghiêm ngặt (dù với N=1000 thì O(N) không gian vẫn chấp nhận được).

Cách Giải thích Logic Bậc thang (Ladder Logic)

// Chỉ là minh họa logic, không phải code chạy
// Chỉ áp dụng khi a[i] <= b[i]

long long solve() {
    long long total_length = 0;
    // Bắt đầu bằng cách chọn hình đầu tiên xoay để chiều rộng lớn nhất
    // Hoặc không xoay, nhưng logic bên dưới sẽ xử lý

    // Thực chất bài toán này có một đặc điểm khi a <= b:
    // Luôn ưu tiên chọn chiều rộng lớn nhất (b[i]) cho mỗi hình.
    // Tuy nhiên, nếu chọn b[i] cho tất cả, có thể không tối ưu nếu a[i] rất nhỏ.
    // Nhưng thực tế lời giải DPRECLINE cho thấy:
    // "Luôn chọn chiều rộng là b[i] (xoay) hoặc a[i] (không xoay) sao cho tổng bằng phẳng"

    // Code mẫu thể hiện ý tưởng "Greedy" (Tham lam) nhưng thực chất DP:
    // Tuy nhiên, có một cách tiếp cận khác:
    // Luôn chọn chiều rộng của hình thứ i là b[i] (xoay).
    // Nếu a[i] <= b[i], việc xoay để có chiều rộng b[i] là cách duy nhất để có độ dài lớn nhất cho đoạn ngang.
    // Vấn đề là chiều cao.

    // Phân tích kỹ:
    // Khoảng cách giữa 2 điểm trên trục Ox là w (chiều rộng).
    // Khoảng cách giữa 2 điểm trên trục Oy là |h1 - h2|.
    // Nếu ta xoay tất cả để lấy b[i] làm w, w là max. Nhưng |h1 - h2| có thể nhỏ.
    // Nếu ta giữ a[i] làm w, w nhỏ hơn nhưng |h1 - h2| có thể lớn hơn.

    // Rõ ràng DP là chính xác nhất.
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Approach này không dùng code thuật toán mà tập trung vào phân tích logic 'Bậc thang'.

Một số người có thể nhầm tưởng rằng bài này là bài tham lam (Greedy) đơn giản: Cứ chọn chiều rộng lớn nhất cho mỗi hình (tức là b[i] nếu a[i] <= b[i]). Tuy nhiên, điều này không đúng hoàn toàn vì tổng độ dài bao gồm cả độ chênh lệch chiều cao.

Ví dụ: Hình 1: 2x5 (rộng 2, cao 5) Hình 2: 3x8 (rộng 3, cao 8)

Nếu chọn rộng lớn nhất (5 và 8):

• Hình 1 xoay: rộng 5, cao 2.
• Hình 2 xoay: rộng 8, cao 3.
• Độ dài: 5 + 8 + |2 - 3| = 13.

Nếu chọn xen kẽ:

• Hình 1 không xoay: rộng 2, cao 5.
• Hình 2 xoay: rộng 8, cao 3.
• Độ dài: 2 + 8 + |5 - 3| = 12.

Do đó, không có giải pháp tham lam đơn giản nào.

Tuy nhiên, có một quan sát quan trọng:

• Nếu ta chọn không xoay hình i (chiều rộng a[i]), chiều cao là b[i].
• Nếu ta chọn xoay hình i (chiều rộng b[i]), chiều cao là a[i].

Vì a[i] <= b[i], ta luôn có:

• Chiều rộng khi không xoay (a) <= Chiều rộng khi xoay (b).
• Chiều cao khi không xoay (b) >= Chiều cao khi xoay (a).

Điều này có nghĩa là:

• Chọn xoay (chiều rộng b[i]) là cách để tăng độ dài đoạn ngang.
• Chọn không xoay (chiều cao b[i]) là cách để tăng độ dốc (nếu cần).

Cấu trúc quy hoạch động là bắt buộc để khám phá tất cả các khả năng.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành các trạng thái dựa trên việc hình hiện tại được xoay hay không.
• Chiều cao của hình trước đó quyết định độ dài đoạn dọc nối với hình hiện tại.
• Vì ai <= bi, luôn có 2 lựa chọn rõ ràng cho mỗi hình: (Rộng=ai, Cao=bi) hoặc (Rộng=bi, Cao=ai).

Lỗi thường gặp

• Sai công thức tính độ dài: Quên cộng thêm phần chênh lệch chiều cao abs(heightcurrent - heightprevious).
• Quản lý biến sai: Trộn lẫn chiều cao của trường hợp xoay và không xoay khi tính toán bước tiếp theo.
• Xử lý dữ liệu đầu vào: Quên ios_base::sync_with_stdio(false); cin.tie(0); có thể gây chậm.