Hãy xem xét cách sử dụng kỹ thuật động quy cắm (plug DP) để giải quyết các bài toán phức tạp.

Bài tập: hdu 1693 Eat the Trees

Trạng thái của đường viền được biểu diễn dưới dạng bit, trong đó 0 đại diện cho có cắm và 1 là không có cắm. Chúng ta sẽ phân loại và chuyển đổi từ trạng thái trước sang trạng thái hợp lệ tiếp theo. Lưu ý rằng sau mỗi hàng, toàn bộ đường viền cần phải dịch trái. Đồng thời, kích thước mảng cần đủ lớn để chứa tất cả các trạng thái.

Mã chính:

int t = 0;
f[t][0] = 1;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        t ^= 1; memset(f[t], 0, sizeof(f[t]));
        int tp; read(tp);
        for (int s = 0; s < (1 << (m + 1)); ++s) if (f[t ^ 1][s]) {
            ll tmp = f[t ^ 1][s];
            int lft = (s >> j) & 1, up = (s >> (j + 1)) & 1;
            if (!tp) {
                if (!up && !lft) f[t][s] += tmp;
            } else {
                f[t][s ^ (3 << j)] += tmp;
                if (up != lft) f[t][s] += tmp;
            }
        }
    }
    t ^= 1; memset(f[t], 0, sizeof(f[t]));
    for (int s = 0; s < (1 << m); ++s) f[t][s << 1] = f[t ^ 1][s];
}

Lưu ý

• Trạng thái bit bắt đầu từ 0 thường thuận tiện hơn.
• Đường viền có tổng cộng m+1 vị trí!

Một vòng lặp

Bài tập: Gym : Pipe layout

Ở đây, chúng ta cần biết mối quan hệ giữa các cắm. Cách dễ hiểu là sử dụng phương pháp biểu diễn nhỏ nhất. Chúng ta sử dụng số giống nhau để biểu diễn các cắm liên thông trên đường viền, nhưng có thể gặp vấn đề khi hai chuỗi số khác nhau lại biểu diễn cùng một trạng thái. Cách xử lý:

Gán số thứ tự cho số không bằng 0 đầu tiên, số thứ hai, v.v., và số 0 luôn là 0. Khi gặp lại số đã xuất hiện, giữ nguyên số thứ tự.

Mã chính:

const int base = 8, mask = 7;
int b[N], bb[N];

inline int encode() {
    memset(bb, -1, sizeof(bb));
    bb[0] = 0;
    int s = 0, bcnt = 0;
    for (int i = m; ~i; --i) {
        if (bb[b[i]] == -1) bb[b[i]] = ++bcnt;
        s <<= 3; s |= bb[b[i]];
    }
    return s;
}

inline void decode(int s) {
    for (int i = 0; i <= m; ++i) {
        b[i] = s & mask;
        s >>= 3;
    }
}

Sử dụng bảng hash để lưu trữ các trạng thái hợp lệ, tối ưu hóa không gian và thời gian, đồng thời giúp đóng gói các hàm.

Mã chính:

const int P = 9973;
struct hashTable {
    int head[NN], nxt[NN], ecnt;
    int state[NN];
    ll val[NN];
    hashTable() {
        memset(head, 0, sizeof(head));
        memset(nxt, 0, sizeof(nxt));
        memset(state, 0, sizeof(state));
        memset(val, 0, sizeof(val));
        ecnt = 0;
    }
    inline void addedge(int s, ll v) {
        int x = s % P;
        for (int i = head[x]; i; i = nxt[i])
            if (state[i] == s) { val[i] += v; return; }
        ++ecnt;
        nxt[ecnt] = head[x];
        val[ecnt] = v;
        state[ecnt] = s;
        head[x] = ecnt;
    }
    inline void clear() {
        memset(head, 0, sizeof(head));
        ecnt = 0;
    }
    inline void Roll() {
        for (int i = 1; i <= ecnt; ++i)
            state[i] <<= 3;
    }
} f[2];

Một đường đi

Đường đi có hai điểm cuối, nên cắm có thể xuất hiện hoặc biến mất đột ngột. Tuy nhiên, chỉ có hai "cắm độc lập" và không vượt quá hai trong quá trình chuyển đổi. Do đó, chúng ta có thể tính số lượng "cắm độc lập" vào trạng thái chuyển đổi, và kết quả cuối cùng sẽ được lấy từ các trạng thái có số lượng "cắm độc lập" là 2.

Mã chính:

for (int c = 0; c <= 2; ++c) {
    for (int s = 1; s <= f[t ^ 1][c].ecnt; ++s) {
        decode(f[t ^ 1][c].state[s]);
        ll tmp = v + f[t ^ 1][c].val[s];
        int lft = b[j], up = b[j + 1];
        if (lft && up) {
            if (lft == up) {
                // Không thể hợp nhất
            } else {
                for (int k = 0; k <= m; ++k)
                    if (b[k] == up) b[k] = lft;
                Push(c, j, 0, 0);
            }
        } else if (lft || up) {
            int id = lft | up;
            if (dn) Push(c, j, id, 0);
            if (rg) Push(c, j, 0, id);
            if (c < 2) Push(c + 1, j, 0, 0);
        } else {
            tmp -= v;
            Push(c, j, 0, 0);
            tmp += v;
            if (dn && rg) Push(c, j, m, m);
            if (c < 2) {
                if (dn) Push(c + 1, j, m, 0);
                if (rg) Push(c + 1, j, 0, m);
            }
        }
    }
}

Lưu ý

• Đảm bảo thứ tự đúng khi encode và decode.
• Sử dụng cơ số là lũy thừa của 2 để tăng tốc độ.
• Nếu tìm thấy s trong bảng hash, hãy thêm giá trị và thoát khỏi hàm.
• encode() và decode(int s) đều từ 0 đến m vì đường viền có thêm một đường dọc.
• Kiểm tra if (bb[b[i]] == -1) thay vì if (!bb[b[i]]).
• Bắt đầu với trường hợp không có cắm nào.