文章目錄

• • 題目分析
  • • 狀態表示
    • 狀態轉移
    • 時間復雜度
  • 題目鏈接

題目分析

題意重述：給定n*m的方格，看能分成多少個1 *2的小方塊。

題目分析:
擺放方塊的時候，先放橫著的，再放豎著的?？偡桨笖档扔谥环艡M著的小方塊的合法方案數。

如何判斷，當前方案數是否合法？ 所有剩余位置能否填充滿豎著的小方塊。可以按列來看，每一列內部所有連續的空著的小方塊需要是偶數個。

這是一道動態規劃的題目，并且是一道 狀態壓縮的dp：用一個N位的二進制數，每一位表示一個物品，0/1表示不同的狀態。因此可以用$0\to 2^N?1（N二進制對應的十進制數）$中的所有數來枚舉全部的狀態。

狀態表示

狀態表示：$f[i][j]$ 表示已經將前 i -1 列擺好，且從第$i?1$列，伸出到第 $i$ 列的狀態是 $j$ 的所有方案。其中j是一個二進制數，用來表示哪一行的小方塊是橫著放的，其位數和棋盤的行數一致。 請看下面的釋義。

解釋：上圖中 i=2，j =10101（二進制數，但是存的時候用十進制） 所以這里的f[i] [j ] 表示的是 所有前i列擺完之后，從第 i-1列伸到 第i列的狀態是10101（第1行伸出來，第3行伸出來，第5行伸出來，其他行沒伸出來）的方案數。

狀態轉移

狀態轉移
既然第 i 列固定了，我們需要看 第i-2 列是怎么轉移到到第 i-1列的（看最后轉移過來的狀態）。假設此時對應的狀態是k（第i-2列到第i-1列伸出來的二進制數，比如00100），k也是一個二進制數，1表示哪幾行小方塊是橫著伸出來的，0表示哪幾行不是橫著伸出來的。

它對應的方案數是 $f[i?1,k]$ ，即前i-2列都已擺完，且從第i-2列伸到第i-1列的狀態為 k 的所有方案數。

這個k需要滿足什么條件呢?

首先k不能和 j在同一行（如下圖）：因為從i-1列到第i列是橫著擺放的1*2的方塊，那么i-2列到i-1列就不能是橫著擺放的，否則就是1 *3的方塊了！這與題意矛盾。所以 k和j不能位于同一行。

既然不能同一行伸出來，那么對應的代碼為(k & j ) ==0 ，表示兩個數相與，如果有1位相同結果就不是0， (k & j ) ==0表示 k和j沒有1位相同， 即沒有1行有沖突。

既然從第i-1列到第i列橫著擺的，和第i-2列到第i-1列橫著擺的都確定了，那么第i-1列 空著的格子就確定了，這些空著的格子將來用作豎著放。如果 某一列有這些空著的位置，那么該列所有連續的空著的位置長度必須是偶數。

總共m列，我們假設列下標從0開始，即第0列，第1列……，第m-1列。根據狀態表示f[i ] [j] 的定義，我們答案是什么呢？ 請讀者返回定義處思考一下。答案是f[m][0]， 意思是 前m-1列全部擺好,且從第m-1列到m列狀態是0（意即從第m-1列到第m列沒有伸出來的）的所有方案，即整個棋盤全部擺好的方案。

時間復雜度

dp的時間復雜度 =狀態表示× 狀態轉移

狀態表示 f[i][j] 第一維i可取11，第二維j（二進制數）可取$2^{11}$ ，所以狀態表示 $11\times 2^{11}$

狀態轉移 也是$2^{11}$
所以總的時間復雜度
$11\times 2^{11}\times 2^{11}\approx 4\times 10^7$ 可以過

ac代碼

/* 下文對 if((j&k )==0 && st[ j| k] ) 有清晰的解釋！！！ */#include<bits/stdc++.h> using namespace std;const int N=12, M = 1<< N; long long f[N][M] ;// 第一維表示列， 第二維表示所有可能的狀態bool st[M]; //存儲每種狀態是否有奇數個連續的0，如果奇數個0是無效狀態，如果是偶數個零置為true。//vector<int > state[M]; //二維數組記錄合法的狀態 vector<vector<int>> state(M); //兩種寫法等價:二維數組 int m , n;int main(){while(cin>>n>>m, n||m){ //讀入n和m，并且不是兩個0即合法輸入就繼續讀入//第一部分：預處理1//對于每種狀態，先預處理每列不能有奇數個連續的0for(int i=0; i< 1<<n; i++){int cnt =0 ;//記錄連續的0的個數bool isValid = true; // 某種狀態沒有奇數個連續的0則標記為truefor(int j=0;j<n;j++){ //遍歷這一列，從上到下if( i>>j &1){ //i>>j位運算，表示i（i在此處是一種狀態）的二進制數的第j位； &1為判斷該位是否為1，如果為1進入ifif(cnt &1) { //這一位為1，看前面連續的0的個數，如果是奇數（cnt &1為真）則該狀態不合法isValid =false;break;} cnt=0; // 既然該位是1，并且前面不是奇數個0（經過上面的if判斷），計數器清零。//其實清不清零沒有影響}else cnt++; //否則的話該位還是0，則統計連續0的計數器++。}if(cnt &1) isValid =false; //最下面的那一段判斷一下連續的0的個數st[i] = isValid; //狀態i是否有奇數個連續的0的情況,輸入到數組st中}//第二部分：預處理2// 經過上面每種狀態 連續0的判斷，已經篩掉一些狀態。//下面來看進一步的判斷：看第i-2列伸出來的和第i-1列伸出去的是否沖突for(int j=0;j< 1<<n;j++){ //對于第i列的所有狀態state[j].clear(); //清空上次操作遺留的狀態，防止影響本次狀態。for(int k=0;k< 1<<n;k++){ //對于第i-1列所有狀態if((j&k )==0 && st[ j| k] ) // 第i-2列伸出來的 和第i-1列伸出來的不沖突(不在同一行) //解釋一下st[j | k] //已經知道st[]數組表示的是這一列沒有連續奇數個0的情況，//我們要考慮的是第i-1列（第i-1列是這里的主體）中從第i-2列橫插過來的，還要考慮自己這一列（i-1列）橫插到第i列的//比如 第i-2列插過來的是k=10101，第i-1列插出去到第i列的是 j =01000，//那么合在第i-1列，到底有多少個1呢？自然想到的就是這兩個操作共同的結果：兩個狀態或。 j | k = 01000 | 10101 = 11101//這個 j|k 就是當前 第i-1列的到底有幾個1，即哪幾行是橫著放格子的state[j].push_back(k); //二維數組state[j]表示第j行， //j表示 第i列“真正”可行的狀態，如果第i-1列的狀態k和j不沖突則壓入state數組中的第j行。//“真正”可行是指：既沒有前后兩列伸進伸出的沖突；又沒有連續奇數個0。}}//第三部分：dp開始memset(f,0,sizeof f); //全部初始化為0，因為是連續讀入，這里是一個清空操作。類似上面的state[j].clear()f[0][0]=1 ;// 這里需要回憶狀態表示的定義，按定義這里是：前第-1列都擺好，且從-1列到第0列伸出來的狀態為0的方案數。//首先，這里沒有-1列，最少也是0列。其次，沒有伸出來，即沒有橫著擺的。即這里第0列只有豎著擺這1種狀態。for(int i=1;i<= m;i++){ //遍歷每一列:第i列合法范圍是(0~m-1列)for(int j=0; j< 1<<n; j++){ //遍歷當前列（第i列）所有狀態jfor( auto k : state[j]) //如果 第i列的狀態j“真正”可行，就轉移f[i][j] += f[i-1][k]; // 當前列的方案數就等于之前的第i-1列所有狀態k的累加。}}//最后答案是什么呢？//f[m][0]表示 前m-1列都處理完，并且第m-1列沒有伸出來的所有方案數。//即整個棋盤處理完的方案數cout<< f[m][0]<<endl;} }

題目鏈接

Acwing291. 蒙德里安的夢想

總結

以上是生活随笔為你收集整理的Acwing291. 蒙德里安的梦想：状态压缩dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。