題目鏈接

[USACO06NOV] Corn Fields G

題解

這是一道典型的狀壓dp，對于 \(M\) 行 \(N\) 列的圖，由于每個點只有 \(1\) 和 \(0\) 兩種狀態，我們將其壓縮為一個長度為 \(M\) 的數組，數組（ \(g\) ）的每一項 \(g_{i}\) 表示狀態的二進制表示法表示的數(如 \(101\) 表示為 \(5\) )，我們預先處理 \(cnt\) 個可能的狀態，將其存放在數組 \(sta\) 當中，我們在用 \(f_{i,j}\) 來表示表示第 \(i\) 行選擇狀態 \(j\) 的最大情況數
易得到狀態轉移方程式：
\( f_{i,j}= \begin{cases} f_{i,j} \\f_{i,j}+f_{i-1,k} \end{cases} \)
其中 \(k\) 表示第 \(i-1\) 行的狀態為 \(sta_{k}\) ，那么對于狀態 \(j\)，它存在的條件是：

• 狀態 \(j\) 必須可以存在于第 \(i\) 行，即不能有原圖上標記為 \(0\) 的點而狀態 \(j\) 上標記為 \(1\) 的點，判斷代碼：

if (sta[i]&(~g[1]));

• 狀態 \(j\) 不能與第 \(i-1\) 行的狀態 \(k\) 沖突，即狀態 \(k\) 上為 \(1\) 的點，狀態 \(j\) 上的這個點不能為 \(1\) ，判斷代碼：

if (sta[k]&sta[j]);

• 同時注意一個細節，在遍歷 \(k\) 時，\(k\) 也要符合第 \(i-1\) 行，即：

if (sta[k]&(~g[i-1]));

對于第一行，要單獨處理，因為不存在第 \(i-1\) 行。對于最后輸出的答案，要把最后一行所有可能的狀態的情況數相加才行

int ans=0;
for (int i=1;i<=cnt;i++) ans+=dp[m][i];

CODE

#include<cstdio>
using namespace std;
#define P 100000000

int m,n;
int g[13];
int sta[5000];      //預處理的所有可能的狀態
int dp[13][5000];   //dp[i][j]表示第i行如果選擇狀態j，最大情況數
int cnt;

void dfs(int s,int t){
    if (t>=n){
        sta[++cnt]=s;
        return;
    }
    dfs(s,t+1);    //當第t+1個點不選
    dfs(s+(1<<t),t+2);    //當第t+1個點選，直接跳轉至t+2對t+2+1的點進行選擇
}

int main(){
    scanf("%d%d",&m,&n);
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            int tmp;
            scanf("%d",&tmp);
            g[i]=g[i]+(tmp<<(n-j));  //處理每一行的狀態（轉換為二進制值）
        }
    }
    dfs(0,0);   //預處理
    for (int i=1;i<=cnt;i++){
        if (sta[i]&(~g[1])) continue;   //判斷狀態i對于第一行是否可選
        else dp[1][i]++;                //如果可選，情況+1
    }//第一行特殊處理
    for (int i=2;i<=m;i++){
        for (int j=1;j<=cnt;j++){
            for (int k=1;k<=cnt;k++){
                if (sta[j]&(~g[i])) continue;   //判斷狀態i對于第i行是否可選
                if (sta[k]&(~g[i-1])) continue; //判斷狀態k對于第i-1行是否可選
                if (sta[k]&sta[j]) continue;    //判斷狀態k和狀態j是否可以作為相鄰的兩行
                dp[i][j]+=dp[i-1][k];           //滿足上述三個條件后，dp[i][j]加上dp[i-1][k]
            }
        }
    }//第二行之后的處理
    int ans=0;
    for (int i=1;i<=cnt;i++) ans+=dp[m][i];  //對最后一行所有可能裝狀態的情況數相加，即為最后的答案
    printf("%d",ans%P);
    return 0;
}