Mato is No.1

原題地址
說實話我第一次嘗試寫炮兵陣地是在2009年……已經(jīng)過去兩年多了，終于找到了一個好的解法……慶祝一下……

【狀態(tài)壓縮DP】
所謂狀態(tài)壓縮DP，就是對于某些DP問題，每一階段的狀態(tài)都有很多維，要利用某些手段將它們壓縮到一維（一個正整數(shù)），順便進行狀態(tài)的精簡（去掉不合法的狀態(tài)），然后再進行DP。這里講的主要是傳統(tǒng)的狀壓DP，有一種基于“插頭”的DP，更高級，以后再搞。
對于本題，可以設(shè)計出一個這樣的狀態(tài)：[0..1][0..1][0..1]...[0..1]（有M個[0..1]），表示該行的每個格子放不放炮兵，如果放，為1，否則為0。顯然，這是一個M位二進制數(shù)，如果能把它們壓縮成一個int就好了。

【如何壓縮】
第一個問題是這么多維的狀態(tài)如何壓縮的問題。
對于本題，由于是二進制數(shù)，直接壓縮就可以了。但是對于某些情況，狀態(tài)是個三進制數(shù)（每個格子的屬性都有3種）甚至更多進制數(shù)，這樣，直接壓縮會導(dǎo)致無法使用位運算，從而使“解壓”變得很麻煩，耗時也很長（需要暴力），因此，可以將每位三進制都拆成兩位二進制：
0->00
1->01
2->10
（當(dāng)然1拆成10、2拆成11也木有問題，只要能區(qū)分開就行了）
這樣，每個狀態(tài)就可以用2個二進制數(shù)來表示，可以在構(gòu)造出所有合法狀態(tài)以后將每個狀態(tài)所對應(yīng)的兩位二進制數(shù)存到struct里面，使用時調(diào)出即可。

【如何精簡】
這個問題是最重要的，因為，如果不精簡，在枚舉狀態(tài)以及轉(zhuǎn)移的時候就會枚舉到很多不合法狀態(tài)，導(dǎo)致時間浪費。
所謂精簡，是指在預(yù)處理以及DP過程中，盡量避開不合法狀態(tài)。
（1）預(yù)處理中的精簡：
包括3個部分：
<1>找到所有可能的合法狀態(tài)并編號：根據(jù)題意限制，有的狀態(tài)在階段內(nèi)就不合法（比如本題，一行一階段，那么凡是有兩個1位的距離小于2的狀態(tài)都不合法），而且這種狀態(tài)所占的比重往往還很大（本題中，M=10時，也只有60種可能的合法狀態(tài)），此時，為了找到這些合法狀態(tài)，可以DFS構(gòu)造實現(xiàn)。
需要注意的是，有的題不光要找到一個階段內(nèi)的合法狀態(tài)，還要找到兩個或兩個以上階段內(nèi)的合法狀態(tài)（比如那個有關(guān)多米諾骨牌的題），此時需要兩個int同時DFS；
在找到合法狀態(tài)以后，需要對每個合法狀態(tài)進行編號，以達到“壓縮”的目的。這里就涉及到了狀態(tài)編號和狀態(tài)表示的問題：比如，狀態(tài)1001，表示為9，在DFS中第一個被搜到，因此編號為0，不要搞混了這兩個（尤其不要搞混“編號為0”和“狀態(tài)表示為0”，它們是不同的）。在預(yù)處理和DP的過程中，所有涉及到狀態(tài)的數(shù)組下標(biāo)，全部是編號而不是表示，知道編號要求表示，可以在DFS中記錄的數(shù)組里面調(diào)，而知道表示要求編號，可以利用逆數(shù)組或者哈希；
<2>找到每一階段的合法狀態(tài)：即使是<1>中被判定為合法的狀態(tài)，在具體的各個階段中也未必合法（比如本題，如果某一行的某一個位置是'H'，不能放，而某一個狀態(tài)在這里放了，則不合法），因此要對每個階段再枚舉一遍，找到真正合法的狀態(tài)，并計入一個vector；
<3>找到狀態(tài)轉(zhuǎn)移中的合法狀態(tài)：在狀態(tài)轉(zhuǎn)移中，往往要求狀態(tài)不沖突（比如本題，在連續(xù)的三個階段中，都不能有某一位有兩個為1的情況），因此，還要枚舉每個狀態(tài)在轉(zhuǎn)移時與其不沖突的狀態(tài)，并計入vector。
注意，有時候這一步不是很容易進行，需要在DP過程中進行；
（2）DP過程中的精簡：
DP過程中，枚舉狀態(tài)、轉(zhuǎn)移決策都只枚舉合法的，在vector里面調(diào)（注意vector里記錄的全都是狀態(tài)編號而不是表示?。?，可以大大減少枚舉量，不過有時候，還會有一些時間浪費，這時候，可以采取一些其它的辦法來精簡，比如再次進行DFS構(gòu)造合法狀態(tài)等。

總之，這類問題的目標(biāo)就是“精簡，精簡，再精簡，使枚舉到的不合法狀態(tài)減到最少”。