Hiểu bài toán

Bài toán yêu cầu tìm chiều cao tối thiểu của một giá sách để chứa n cuốn sách xếp theo thứ tự và chia thành các tầng. Mỗi tầng có độ rộng tối đa là L và chiều cao bằng với cuốn sách cao nhất trong tầng đó. Chiều cao tổng của giá sách là tổng chiều cao của tất cả các tầng. Ta cần chia n cuốn sách thành các nhóm liên tiếp (tầng) sao cho tổng chiều cao các nhóm là nhỏ nhất, với ràng buộc tổng chiều rộng của mỗi nhóm không vượt quá L.

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

Cách Quy hoạch động cơ bản (Bộ nhớ O(n^2))

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

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

    int n;
    long long L;
    cin >> n >> L;
    vector<long long> h(n + 1), w(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> w[i];
    }

    const ll INF = 1e18;
    vector<ll> dp(n + 1, INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        ll maxH = 0;
        ll currentW = 0;
        // Duyệt ngược từ i về 1 để thử các nhóm cuối cùng
        for (int j = i; j >= 1; j--) {
            currentW += w[j];
            if (currentW > L) break;
            maxH = max(maxH, h[j]);
            dp[i] = min(dp[i], dp[j - 1] + maxH);
        }
    }

    cout << dp[n];
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Dùng mảng dp[i] lưu chiều cao tối thiểu để xếp i cuốn sách đầu tiên. Để tính dp[i], ta xét tất cả các vị trí j (từ i về 1) để phân chia: các cuốn từ j đến i xếp vào một tầng cuối cùng, và các cuốn trước j đã được xử lý với chi phí dp[j-1]. Trong quá trình duyệt ngược, ta cập nhật độ rộng tích lũy và chiều cao lớn nhất của tầng hiện tại. Nếu độ rộng vượt quá L thì dừng lại. Độ phức tạp là O(n^2) do có 2 vòng lặp lồng nhau.

Cách Quy hoạch động với Truy vết (Bộ nhớ O(n^2))

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

vector<long long> prefix(2005,0);
vector<long long> dp(2005,1e9+1);

int main(){
    int n,l,sum=0;
    cin>>n>>l;
    vector<int> w(n+1),h(n+1,-1);
    for(int i=1;i<=n;i++){
        cin>>h[i]>>w[i];
        sum+=w[i];
        prefix[i]=sum;
    }
    dp[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(prefix[i]-prefix[j]<=l){
                dp[i] = min(dp[i],dp[j]+(*max_element(h.begin()+j+1,h.begin()+i+1)));
            }
        }
    }
    cout<<dp[n];
}

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

Cách này sử dụng mảng cộng dồn (prefix sum) để kiểm tra nhanh độ rộng của nhóm sách từ j+1 đến i. Tuy nhiên, việc sử dụng max_element trong vòng lặp để tìm chiều cao lớn nhất khiến cho hiệu năng thực tế kém hơn so với việc cập nhật dần khi duyệt ngược. Logic vẫn là chia dãy con cuối cùng, nhưng cách cài đặt này ít hiệu quả hơn do truy cập bộ nhớ không tuần tự và thao tác tìm max lặp lại.

Cách Quy hoạch động tối ưu (Duyệt ngược)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long

signed main(){
  int n,l;cin>>n>>l;
  vector<int>h(n+1,0);
  vector<int> w(n+1,0);
  for(int i=1;i<=n;i++){
    cin>>h[i]>>w[i];
  }
  vector<int>dp(n+1,1e18);
  dp[0]=0;
  for(int i=1; i<=n;i++){
    int he=0, we=0;
    // Duyệt ngược từ i về 1 để xây dựng tầng cuối cùng
    for (int j=i;j>0;j--){
      we+=(w[j]);
      he=max(he,h[j]);
      if(we>l) break;
 dp[i]=min(dp[i],dp[j-1]+he);
    }
  }
  cout<<dp[n]<<endl;
  return 0;
}

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

Đây là phiên bản hiệu quả và phổ biến nhất cho ràng buộc N <= 2000. Ta tính dp[i] là chiều cao tối thiểu của i cuốn sách đầu tiên. Với mỗi i, ta duyệt ngược j từ i về 1 để xác định nhóm sách cuối cùng (từ j đến i). Trong khi duyệt ngược, ta duy trì độ rộng tích lũy we và chiều cao lớn nhất he của nhóm này. Nếu we vượt L, ta dừng vòng lặp ngay lập tức. Phép toán dp[i] = min(dp[i], dp[j-1] + he) được thực hiện trong vòng lặp này. Cách này đảm bảo mỗi cặp (i, j) chỉ xét một lần và tối ưu việc tính toán chiều cao.

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

Bài học kinh nghiệm

• Bài toán có tính chất tối ưu con (Optimal Substructure): Chiều cao tối thiểu của i cuốn sách phụ thuộc vào chiều cao tối thiểu của các tập sách con trước đó.
• Thứ tự xếp sách là bắt buộc, do đó ta chỉ cần chia dãy thành các đoạn liên tiếp.
• Với mỗi trạng thái dp[i], ta chỉ cần quan tâm đến cách chia của đoạn cuối cùng (tầng cuối cùng).

Lỗi thường gặp

• Lưu ý thứ tự duyệt: Nếu duyệt xuôi để tính nhóm cuối cùng, việc tính toán chiều cao lớn nhất của nhóm sẽ phức tạp. Duyệt ngược (từ i về 1) là cách tự nhiên nhất để cập nhật maxHeight của nhóm đang xét.
• Sử dụng kiểu dữ liệu sai: Chiều cao và độ rộng có thể lên tới 10^9, tổng chiều cao có thể lớn. Cần dùng long long (hoặc int64_t) để tránh tràn số.
• Quên kiểm tra sumW > L: Nếu không break vòng lặp kịp thời, độ rộng tích lũy có thể vượt quá giới hạn và tạo ra các trạng thái không hợp lệ.