Skip to content

Quy hoạch động trên Profile gãy. Bài toán "Parquet" (Dynamic Programming on Broken Profile. Problem "Parquet")

Các bài toán phổ biến được giải quyết bằng DP trên profile gãy (broken profile) bao gồm:

  • tìm số cách để lấp đầy hoàn toàn một diện tích (ví dụ: bàn cờ/lưới) bằng một số hình (ví dụ: domino)
  • tìm một cách để lấp đầy một diện tích với số lượng hình tối thiểu
  • tìm một cách lấp đầy một phần với số lượng không gian chưa lấp đầy tối thiểu (hoặc các ô, trong trường hợp lưới)
  • tìm một cách lấp đầy một phần với số lượng hình tối thiểu, sao cho không thể thêm hình nào nữa

Bài toán "Parquet" (Problem "Parquet")

Mô tả bài toán. Cho một lưới kích thước $N \times M$. Tìm số cách để lấp đầy lưới bằng các hình có kích thước $2 \times 1$ (không được để lại ô nào chưa lấp đầy, và các hình không được chồng lên nhau).

Đặt trạng thái DP là: $dp[i, mask]$, trong đó $i = 1, \ldots N$ và $mask = 0, \ldots 2^M - 1$.

$i$ đại diện cho số hàng trong lưới hiện tại, và $mask$ là trạng thái của hàng cuối cùng của lưới hiện tại. Nếu bit thứ $j$ của $mask$ là $0$ thì ô tương ứng đã được lấp đầy, ngược lại nó chưa được lấp đầy.

Rõ ràng, câu trả lời cho bài toán sẽ là $dp[N, 0]$.

Chúng ta sẽ xây dựng trạng thái DP bằng cách lặp qua từng $i = 1, \cdots N$ và từng $mask = 0, \ldots 2^M - 1$, và với mỗi $mask$ chúng ta sẽ chỉ chuyển tiếp, tức là, chúng ta sẽ thêm các hình vào lưới hiện tại.

Cài đặt (Implementation)

int n, m;
vector < vector<long long> > dp;


void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
    if (x == n)
        return;
    if (y >= m)
        dp[x+1][next_mask] += dp[x][mask];
    else
    {
        int my_mask = 1 << y;
        if (mask & my_mask)
            calc (x, y+1, mask, next_mask);
        else
        {
            calc (x, y+1, mask, next_mask | my_mask);
            if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
                calc (x, y+2, mask, next_mask);
        }
    }
}


int main()
{
    cin >> n >> m;

    dp.resize (n+1, vector<long long> (1<<m));
    dp[0][0] = 1;
    for (int x=0; x<n; ++x)
        for (int mask=0; mask<(1<<m); ++mask)
            calc (x, 0, mask, 0);

    cout << dp[n][0];

}

Bài tập (Practice Problems)

Tài liệu tham khảo (References)