$\text{🌱 Một kiểu tối ưu quy hoạch động trạng thái}$

---

🔗 Link:

📌 Tags: Tutorial, DP-Bitmask

👤 Writer: @madv809

👥 Contributor: @SPyofgame

📋 Content:

• • Đôi lời giới thiệu :
  • Rồi giờ mình vào phần chính thôi
• Tổng quan :

Đôi lời giới thiệu :

Chào mọi người, mình là thành viên của nhóm Editorial Slayers. Mình chia sẻ bài viết này như một cp blog bình thường nên là mong mọi người đừng ném đá nhé :D

//btw mục đích của bài viết cũng là để note lại và chia sẻ. Lưu ý rằng bài viết này không dành cho những bạn chưa biết đến quy hoạch động trạng thái (dp state). Mình khuyên các bạn nên skip nếu chưa từng nghe đến khái niệm trên, cơ mà nếu thích thì các bạn vẫn cứ đọc thôi :P

Rồi giờ mình vào phần chính thôi

Cách đây vài hôm, trong lúc đang làm bài thì mình đã gặp một dạng bài dp trạng thái có cách đặt state rất hay. Cách đặt dp kiểu như vậy khi mới học dp state mình đã gặp một lần trong lúc đọc editorial của một anh nào đó mình không nhớ rõ vì cách đây cũng khá lâu rồi. Chia sẻ thêm là lúc đấy dp state cơ bản mình cũng chưa nắm rõ nên đọc solution của người viết mình cũng mập mờ và không hiểu mô tê gì hết :/

Thế cho nên là khi gặp lại dạng này, mình không nhận ra được và đã TLE sml. Tuyệt vọng vì tưởng máy chấm vnoj yếu (mà thật ra là do thuật mình chưa đúng chứ máy chấm vnoj yếu thật mà) thì mình quyết định nhá qua sol, sượt qua hình minh họa, mình nhận ra ngay rằng đã gặp kiểu dp này trong quá khứ rồi (nói quá khứ thì nghe hơi xưa nhỉ :/). Và mình cảm thấy rất phấn khích đến mức muốn note lại ngay cái mình vừa nhớ ra lúc đó.

Cụ thể là bài tập này trên vnoj

Tóm tắt :

Cho một bảng gồm

$N$ hàng

$M$ cột (

$N$

$⩽$ 1000,

$M$

$⩽$ 10), mỗi ô trên bảng là một kí tự # hoặc

$.$ tương ứng cho ô đang mở và ô đang đóng. Bạn được cho một cuộn băng dính dài vô tận, và nó có chiều rộng bằng một ô trên bảng. Bạn có thể xé một đoạn băng dính và dùng nó để dán một đoạn liền kề những ô cửa sổ đã đóng theo chiều dọc hoặc chiều ngang. Hỏi số đoạn cần dùng ít nhất là bao nhiêu.

Chà, chắc bạn đang nghĩ bài này khá dễ, vì

$M$ bé nên chỉ cần gọi

$f[i][mask]$

$=$ số cách tối ưu khi dán đến hàng

$i$ và các trạng thái băng dính trên hàng

$i$ là

$mask$, với

$mask$ là các bit

$01$.

$0$ biểu diễn cho ô dán băng dính ngang hoặc ô đang đóng,

$1$ biểu diễn cho ô dán băng dính dọc. Chuyển trạng thái thì chỉ cần viết thêm 1 hàm tính chi phí cho 2 cái

$mask$ đang xét là xong.

Cơ mà đánh giá đpt thì tầm

$N\ast M\ast 2^{2M}$
với

$N\ast 2^M$ là số trạng thái,

$2^M\ast M$ là chi phí chuyển

$state$ + chi phí tính

$cost$ của 2

$mask$ mỗi lần chuyển trạng thái. Nhìn thì có vẻ không AC. Tuy nhiên mình thử prune tí nhé (ý là xem xem có gì có thể bỏ qua để tối ưu không ý mà).

Với mỗi hàng, không hẳn số trạng thái của nó sẽ là

$2^M$ vì có thể có sự xuất hiện của các ô

$.$ , mình thử dùng 1 vector để lưu lại các trạng thái này và chỉ duyệt các trạng thái có trên các vector này thôi.

Thêm cái nữa là nhận thấy khi chuyển từ

$f[i-1][mask1]\to f[i][mask2]$ thì nó chỉ bị tăng lên 1 lượng không quá

$M$, (bạn có

$M$ ô mỗi hàng, giờ tối đa là

$M$ miếng băng dính nên lượng tăng lên cũng không quá

$M$). Gọi

$min\mathrm{\_}mask$ là giá trị nhỏ nhất của các

$f[i][mask]$, mình sẽ pop ra hết trong vector lưu trạng thái đã được đề cập ở trên thằng nào có

$f[j][mask]>min\mathrm{\_}mask+M$. Nghe có vẻ hợp lí rồi đấy, chắc đây là thứ người ra đề muốn mình làm, test thử thôi!

"Sặc, TLE sml rồi, prune như thế cũng không được nốt. Hmmm…"

Đánh giá lại cách làm trên, trong trường hợp xấu nhất là các ô đều là

$.$ thì cách prune trên cũng không mang lại được gì trừ trường hợp người ra đề muốn mình làm thế, cho nên chắc hẳn sol chuẩn phải là một cái gì đó khác.
Sau một hồi lâu suy nghĩ thì mình đã chịu thua, vì ngoài cách dp như trên, mình không còn nghĩ ra được gì khác, đã đến lúc để đọc sol:v

Mình vửa mở sol lên, lướt xuống thì thấy hình ảnh này hiện lên

"aduuuuuuuuu"

Đó là cảm giác của mình lúc đấy, mình đã nhận ra cách đặt state dp cho bài này. Cảm thấy nó thật ảo diệu vì lâu rồi mình mới gặp lại nó (mà nó đã ảo diệu từ đầu rồi).

Cụ thể, bạn gọi

$dp[i][j][mask]$ là cách tối ưu khi xét đến hàng thứ

$j$, từ bit

$0$ đến bit

$j-1$ biểu diễn trạng thái của hàng thứ

$i$ tại các cột

$0...j-1$. Các bit

$j...m-1$ biểu diễn trạng thái của hàng

$i-1$ tại các cột

$j...m-1$ (do làm trên bit index từ

$0$, nên số cột mình cũng index từ

$0$ luôn cho nó dễ). Để cho dễ hình dung, trên hình ô màu đỏ là ô

$dp$ ta đang xét, các ô xanh dương sẽ là các bit trong

$mask$ của chúng ta (tất nhiên là bao gồm cả ô màu đỏ).

wait, dừng khoảng chừng là 2s, tại sao lại có cách đặt trạng thái lạ thế?
Đơn giản là vì nó sẽ chuyển trạng thái được trong

$O(1)$, yep, mình không đùa đâu, chúng ta có

$M\ast N\ast 2^M$ trạng thái và chúng ta chuyển trong

$O(1)$. Và cũng chính vì cách đặt state rất lạ này mà nó khiến mình cảm thấy rất thích thú, ảo ma thật đấy :D.

Rồi giờ chuyển state như thế nào, nói ra khá dài dòng nên mình sẽ để các bạn đọc code rồi rút ra kết luận nhé :P

Code

#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b - 1); ++i)

    REP(i, 2, n) FOR(j, 0, m) FOR(mask, 0, mx)
    {
        f[i][j][mask] = INF;
        REP(tt, 0, 1)
        {
            bit1 = mask >> j & 1; bit2 = bit1^tt;
            if (j == 0)
            {
                if (bit1 == 1)
                {
                    if ((s[i][j] != '.') && (s[i - 1][j] == '.' || bit2 == 0))
                        minimize(f[i][j][mask], f[i - 1][m - 1][mask^(tt << j)] + 1);
                    else minimize(f[i][j][mask], f[i - 1][m - 1][mask^(tt << j)]);
                }
                else minimize(f[i][j][mask], f[i - 1][m - 1][mask^(tt << j)] + (s[i][j] != '.'));
            }
            else
            if (bit1 == 1)
            {
                if ((s[i][j] != '.') && (s[i - 1][j] == '.' || bit2 == 0))
                    minimize(f[i][j][mask], f[i][j - 1][mask^(tt << j)] + 1);
                else minimize(f[i][j][mask], f[i][j - 1][mask^(tt << j)]);
            }
            else
            {
                if ((s[i][j] != '.') && (s[i][j - 1] == '.' || (mask >> (j - 1) & 1) == 1))
                    minimize(f[i][j][mask], f[i][j - 1][mask^(tt << j)] + 1);
                else minimize(f[i][j][mask], f[i][j - 1][mask^(tt << j)]);
            }
        }
    }

code của mình trông rất xấu và dài dòng, tất nhiên là có cách code ngắn gọn hơn rất nhiều bằng cách dùng vector và loại bỏ luôn 1 chiều của trạng thái, cách này code rất gọn

Code

	vector <int> dp(1 << m, inf), novi(1 << m);
	dp[0] = 0;
	REP(i, n) {
		REP(j, m) {
			REP(k, 1 << m) {
				if(k & (1 << j)) {
					if(mat[i][j] == '.') novi[k] = inf;
					else novi[k] = min(dp[k], dp[k ^ (1 << j)] + 1);
				}
				else {
					novi[k] = min(dp[k], dp[k ^ (1 << j)]);
					if(mat[i][j] == '#' && (j == 0 || (k & (1 << (j - 1))) || mat[i][j - 1] == '.')) novi[k]++;
				}
			}
			dp = novi;
		}
	}

Tổng quan :

Time:

$O(N\ast M\ast 2^M)$
Space:

$O(N\ast M\ast 2^M)$

---

Đấy là những gì mình học được từ cách dp trên, đến đây là hết rồi, nếu bạn thấy bài viết này hay thì hãy nhớ theo dõi nhóm Editorial Slayers tụi mình để đón chờ những bài viết khác nữa nhé, chúc các bạn có một ngày học tập và làm việc thật tốt.