【題目鏈接】

ybt 1593：【例 2】牧場的安排
洛谷 P1879 [USACO06NOV] Corn Fields G

【題目考點】

1. 狀壓動規

【解題思路】

集合狀態：n個元素中，選擇x個元素構成的集合，可以由一個n位二進制數表示。第i位為1表示選擇第i個元素，第i位為0表示不選擇第i個元素。
將在某格子種草稱為為該格子著色。
本題每行著色的情況可以設為一個集合狀態，稱為著色狀態。第i位為1表示選擇了這一行的第i個格子已著色，第i位為0表示第i個格子沒有著色。

設$s_i$表示第i行的土地狀態，$s_i$第j位為1表示第i行第j個格子可以著色，為0表示不可以著色。

二進制下的數字位，從0開始，從低位到高位分別是第0位，第1位。。。
例：二進制數：110 ：第0位為0， 第1位為1，第2位為1

解法1：狀壓動規 枚舉所有狀態

狀態定義

• 階段：前i行，第i行的著色為集合狀態j
  第i+1行的集合狀態受到第i行著色狀態的影響，因此階段之一需要是第i行的著色狀態。
• 決策：決定一行的著色
• 策略：網格圖的著色方案
• 策略集合：對前i行著色，且第i行著色為集合狀態j的所有著色方案
• 統計量：方案數

狀態定義$d{p}_{i,j}$：對前i行著色，且第i行著色為集合狀態j的著色方案總數。

狀態轉移方程

• 策略集合：對前i行著色，且第i行著色為集合狀態j的所有著色方案
• 分割策略集合：根據第i-1行的不同著色狀態來分割策略集合

在求$d{p}_{i,j}$時，要枚舉第i行的所有著色狀態j，從中篩選出符要求的著色狀態。在此過程中需要枚舉第i-1行所有可能的著色狀態，設枚舉出的第i-1行的著色狀態為k。

1. 著色的格子必須是這一行可以著色的格子的子集

   因此第i行的著色狀態j表示的已著色的格子必須是$s_i$表示的已著色的格子的子集，即必須滿足s[i] & j == j。
   第i-1行的著色狀態k表示的已著色的格子必須是$s_{i?1}$表示的已著色的格子的子集，即必須滿足s[i-1] & k == k。

2. 每一行不可以有相鄰的兩個格子都著色。
   將k左移一位k<<1，k<<1中第i位數為k中第i-1位數。k<<1的最低位為0。
   那么k<<1 & k的結果，就是將k的每一位與其右側相鄰一位進行按位與運算，（由于k<<1最低位為0，那么按位與的結果最低位為0）
   如果存在k的相鄰兩位都是1，那么結果不為0。如果不存在k的相鄰兩位都是1，那么結果為0。
   因此第i-1行只有滿足(k<<1 & k) == 0（或寫為!(k<<1 & k)）的著色狀態符合要求。同理第i行只有滿足!(j << 1 & j)的著色狀態符合要求。

3. 第i行的著色狀態j與第i-1行的著色狀態k同一列的格子不能都著色。
   也就是這兩個二進制數同一數位上不能都為1。
   如果k與j某一位都為1，那么k & j不為0，否則為0。
   因此k與j需要滿足(k & j) == 0（或寫為!(k & j)），才不存在第i行與第i-1行縱向上有相鄰的格子都著色。

對于第i行的符合要求的著色狀態j，找到一個符合要求的第i-1行的著色狀態k，對前i-1行著色且第i-1行的著色狀態為k的著色方案數為$d{p}_{i?1,k}$。
對i-1行所有滿足條件的著色狀態k，將$d{p}_{i?1,k}$加和，即為對前i行著色且第i行著色狀態為j的著色方案數。
因此$d{p}_{i,j}=\sum d{p}_{i?1,k}$，j需要滿足j & s[i] == j，k需要滿足k & s[i-1] == k && !(k<<1 & k) && !(k & j)。

對于初始狀態，本題可以枚舉第一行滿足沒有相鄰格子染色（即滿足j & s[1] == j && !(j<<1 & j)）的染色狀態j，第一行染色狀態為j的方案有一種，設$d{p}_{1,j}=1$。

或者假設第0行參與染色，第0行只存在染色狀態為0的一種情況，因此設$d{p}_{0,0}=1$

最后對于第m行的所有符合j & s[m] == j的狀態j，求出為前m行染色，第m行著色狀態為j的方案數，并加和。即結果為$\sum d{p}_{m,j}$，j滿足j & s[m] == j。

注意，每次加和后都要對$10^8$取模。

解法2：狀壓動規 保存合法的狀態

本題每一行只會取沒有相鄰格子著色的狀態，那么可以先將這些一定沒有相鄰格子同時著色的集合狀態預處理出來，保存在state數組，state[i]表示第i個可用的集合狀態。
而后$d{p}_{i,j}$表示的是對前i行著色，且第i行著色狀態為state[j]的方案數。
接下來在判斷著色狀態是否符合要求時，就不用判斷“要求相鄰格子不能同時著色”這一點了，即不用再寫j<<1 & j與k<<1 & k。

【題解代碼】

解法1：狀壓動規 枚舉所有狀態

• 寫法1：設第1行的狀態作為初始狀態

#include<bits/stdc++.h>
using namespace std;
const int N = 12+5, S = (1<<12)+5, M = 1e8;
int m, n, s[N];//s[i]：第i行可以種草的集合狀態 1表示可以種，0表示不可以種 
long long dp[N][S], ans;//dp[i][j]：前i行著色，第i行集合狀態為j的方案數 
int main()
{int x;cin >> m >> n;for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j){cin >> x;s[i] = s[i]<<1 | x;}for(int j = 0; j < 1<<n; ++j) if((j & s[1]) == j && !(j & j<<1))//j不是s[i]的子集 或 j有相鄰的著色格 dp[1][j] = 1;for(int i = 2; i <= m; ++i)for(int j = 0; j < 1<<n; ++j) if((j & s[i]) == j && !(j & j<<1))//j是s[i]的子集 同時 j沒有相鄰的著色格 for(int k = 0; k < 1<<n; ++k) if((k & s[i-1]) == k && !(k & k<<1) && !(k & j))//k不是s[i-1]的子集，或k有相鄰著色格，或k與j有上下相鄰的著色格 dp[i][j] = (dp[i][j]+dp[i-1][k])%M; for(int j = 0; j < 1<<n; ++j) if((j & s[m]) == j && !(j & j<<1))ans = (ans+dp[m][j])%M;cout << ans;return 0;
}

• 寫法2：設第0行的狀態作為初始狀態

#include<bits/stdc++.h>
using namespace std;
const int N = 12+5, S = (1<<12)+5, M = 1e8;
int m, n, s[N];//s[i]：第i行可以種草的集合狀態 1表示可以種，0表示不可以種 
long long dp[N][S], ans;//dp[i][j]：前i行著色，第i行集合狀態為j的方案數 
int main()
{int x;cin >> m >> n;for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j){cin >> x;s[i] = s[i]<<1 | x;}dp[0][0] = 1;for(int i = 1; i <= m; ++i)for(int j = 0; j < 1<<n; ++j) if((j & s[i]) == j && !(j & j<<1))//j是s[i]的子集 同時 j沒有相鄰的著色格 for(int k = 0; k < 1<<n; ++k) if((k & s[i-1]) == k && !(k & k<<1) && !(k & j))//k不是s[i-1]的子集，或k有相鄰著色格，或k與j有上下相鄰的著色格 dp[i][j] = (dp[i][j]+dp[i-1][k])%M; for(int j = 0; j < 1<<n; ++j) if((j & s[m]) == j && !(j & j<<1))ans = (ans+dp[m][j])%M;cout << ans;return 0;
}

解法2：狀壓動規 保存合法的狀態

#include<bits/stdc++.h>
using namespace std;
const int N = 12+5, S = (1<<12)+5, M = 1e8;
int m, n, s[N];//s[i]：第i行可以種草的集合狀態 1表示可以種，0表示不可以種 
int state[S], sn;//state[i]：第i個符合條件的集合狀態 
long long dp[N][S], ans;//dp[i][j]：前i行著色，第i行集合狀態為state[j]的方案數 
int main()
{int x;cin >> m >> n;for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j){cin >> x;s[i] = s[i]<<1 | x;}for(int i = 0; i < 1<<n; ++i) if((i & i<<1) == 0)state[++sn] = i;//把沒有相鄰的著色格的集合狀態加入state for(int j = 1; j <= sn; ++j) if((state[j] & s[1]) == state[j])dp[1][j] = 1;for(int i = 2; i <= m; ++i)for(int j = 1; j <= sn; ++j) if((state[j] & s[i]) == state[j])//j不是s[i]的子集 for(int k = 1; k <= sn; ++k) if((state[k] & s[i-1]) == state[k] && !(state[k] & state[j]))//k不是s[i-1]的子集，或k有相鄰著色格，或k與j有上下相鄰的著色格 dp[i][j] = (dp[i][j]+dp[i-1][k])%M;for(int j = 1; j <= sn; ++j) if((state[j] & s[m]) == state[j])ans = (ans+dp[m][j])%M;cout << ans;return 0;
}