ZOJ 2126. Rocket Mania

http://acm.bnu.edu.cn/v3/problem_show.php?pid=15645
http://cojs.tk/cogs/problem/problem.php?pid=1514

Brief description:

瘋狂火箭(Rocket Mania)是幻想遊戲系列中我最喜歡的遊戲之一。在這個遊戲中,左邊有一些火柴,右邊有一些火箭。在中間,有許多種類的帶有導火索的格子。這些導火索可以被旋轉0,90,180或270度。為了發射火箭,必須用導火索形成一條從火柴到火箭的連續通道。當一條完整的通路建立的時候,連接著火柴的所有火箭都將被發射。

你的任務是,給出初始情況,旋轉一些導火索,使點燃某一根火柴後,發射的火箭數量盡量多。

Analysis:

演算法分析
確立狀態:按照從左到右,從上到下的順序依次考慮每一個格子,我們需要記錄每個插頭是否已經點燃以及它們之間的連通情況.因此狀態為 f(i, j, S, fired) 表示轉移完(i, j),輪廓線上10個插頭的連通性為S(把每個插頭是否存在記錄在S中), 10個插頭是否被點燃的2進位數fired的狀態能否達到.
那麼最後的答案為所有可以達到的狀態 f(i, j, S, fired) 中 Ones[fired]的最大值,其中 Ones[x]表示二進位數 x 的 1 的個數。
狀態轉移:依次枚舉每一個格子的旋轉方式 (最多4種),根據當前格子是否可以與上面的格子和左邊的格子通過插頭連接起來分情況討論,O(m) 掃描計算出新的狀態.前面的題目我們已經很詳細地介紹過棋盤模型的問題的轉移方法,這裡不再贅述.

獨立插頭,插頭的轉移十分靈活,且至多會出現 m 個不同的獨立插頭,因而優先考慮最小表示法描述上面的狀態 S。
然後還需要記錄,每個位置的插頭是否處於引燃的狀態(也可以記錄每個種類的插頭是否處於引燃狀態,雖然轉移上常數可能會小、但是統計答案以及剪枝時會比較麻煩。)

用類似 HDU 5374. Tetris 的方法,用四位二進位數,預處理出每種插頭的旋轉。

void Init(){
    
    // 1 Left
    // 2 Up
    // 4 Down
    // 8 Right
    
    // '.'
    Pattern[0].PB(0);
    // '-'
    Pattern[1].PB(1|8); Pattern[1].PB(2|4);
    // 'L'
    Pattern[2].PB(2|8); Pattern[2].PB(8|4); Pattern[2].PB(4|1); Pattern[2].PB(1|2);
    // 'T'
    int U = 15;
    Pattern[3].PB(U^1); Pattern[3].PB(U^2); Pattern[3].PB(U^4); Pattern[3].PB(U^8);
    // '+';
    Pattern[4].PB(U);
}

轉移時各種討論、看上插頭和左插頭的狀態得到下插頭和右插頭的狀態。


                ECH(it, Pattern[A[i][j]]){
                
                    decode(H[src].state[ii]);
                    
                    int p = *it;
                    
                    int lt = b[j], up = b[j+1];
                    bool lt2 = _1(p,0) && lt, up2 = _1(p,1) && up; 
//需要同時判斷格子所在的插頭和狀態所在的插頭同時為真。
                    bool BurN = ((lt2 && _1(BurNing, j)) || (up2 && _1(BurNing, j+1)));
//並且如果有一處引燃,則生成的新插頭也引燃並且如果發生合併則合併過後的插頭也。
                    
                    b[j] = b[j+1] = 0;
                    BurNing &= ~_1(j);
                    BurNing &= ~_1(j+1);
                    
                    int t;

                    if (lt2 && up2){ // 合併插頭,如果有一個引燃則將所有位置等於這兩個插頭的狀態全部置於引燃。
                        t = up;
                        REP(k, m+1) if (b[k] == lt || b[k] == up){
                            if (BurN) BurNing |= _1(k);
                            b[k] = t;
                        }
                    }
                    else if (lt2 | up2){ 
                        if (lt2) t = lt; else t = up;
                    }
                    else{ // 注意最多會產生 m 個插頭,因而新產生的插頭要填 m+1。
                        t = m+1;
                    }
                    
                    if (_1(p,2)){ // 是否產生下插頭
                        b[j] = t;
                        if (BurN) BurNing |= _1(j);
                    }
                    
                    if (_1(p,3) && j != m-1){ // 是否產生右插頭
                        b[j+1] = t;
                        if (BurN) BurNing |= _1(j+1);
                    }
                    
                    if (!BurNing) continue; // Cut-1
                
                    RST(bb); REP(k, m+1) if (b[k]) ++bb[b[k]];
                    REP(k, m+1) if (bb[b[k]] == 1 && !_1(BurNing, k)) b[k] = 0; // Cut-2
                    
                    LL s = encode(); _des.push_back(s);
                    if (count_bits(BurNing) > best){
                        best = count_bits(BurNing);
                        critical = s;
                    }
                }

如果直接按照上面的思路作動態規劃,Sample也需要運行> 60s,實在令人無法滿意.優化,勢在必行.如何通過剪枝優化來減少擴展的狀態總數,儘可能捨去無效狀態成為了現在所面臨的問題:
剪枝通常可以分為兩類:一.可行性剪枝,即將無論之後如何決策,都不可能滿足題目要求的狀態剪掉;二.最優性剪枝,即對於最優性問題,將不可能成為最優解的狀態給剪掉.我們從這兩個角度入手來考慮問題:

  • 剪枝一:如果輪廓線上所有的插頭全部都未被點燃,那麼最後所有的火箭都不可能發射,所以這個狀態可以捨去.這個剪枝看上去非常顯然,對於大部分數據卻可以剪掉近乎一半的狀態.
  • 剪枝二:如果輪廓線上有一個插頭p,它沒有被火柴點燃且沒有其它的插頭與它連通,那麼這個插頭可以認為是「無效」插頭.因為即使這個插頭所在的路徑以後會被點燃而可以發射某個火箭,那麼一定存在另一條路徑可以不經過這個插頭而發射火箭,如圖.這種情況下將插頭設置為不存在.這是最重要的一個剪枝,大部分數據的狀態總數可以縮小七八倍,甚至十幾倍.
  • 剪枝三:這是一個最優性問題,我們考慮最優性剪枝:對於一個格子(i, j)的兩個狀態 (S0, Fired0), (S1, Fired1),如果第一個狀態的每一個存在的插頭在第二個狀態中不僅存在而且都被點燃,那麼無論以後如何決策,第二個狀態點燃的火箭個數不會少於第一個狀態,這樣我們就可以果斷地捨去第一個狀態.對於每一個(i, j),選擇Ones[Fired]最多的一個狀態Best,如果一個狀態一定不比Best好,就可以捨去.

  • 剪枝四:從邊界情況入手,邊界狀態非常特殊,也非常容易導致產生無效狀態.分析一下,轉移完最後一列的某個格子(i, 6)後,如果I類插頭中某個插頭p沒有被點燃,並且II類插頭中沒有插頭與它連通,那麼這個插頭就成了「無效」插頭.

比較以上四種剪枝的效果,由於不同的棋盤初始狀態擴展的狀態總數差異較大,因此選取10組不同的棋盤初始狀態來測試擴展狀態的總數.10組數據大致分布如下:Test 1~4依次為全部「—」,「L」,「T」,「+」,Test 5為奇數行「L」,偶數行為空,Test 6為「L」,「T」交替.Test 7~10為隨機數據,「L」,「T」分布較多,Test 10的「—」較多.

注意,上面的剪枝三,如果對每個狀態都找是否有一個狀態可以完整覆蓋的話,代價太大。
因此採用的是一種折衷的策略,只記錄 Fired 最多的狀態,進行剪枝。

https://gist.github.com/lychees/085c994a7bedb29154bd