【本文比較適合有一定動(dòng)態(tài)規(guī)劃和位運(yùn)算基礎(chǔ)的童鞋閱讀】
首先先講講什么是狀態(tài)壓縮
狀態(tài)壓縮就是使用某種方法，簡明扼要地以最小代價(jià)來表示某種狀態(tài)，通常是用一串01數(shù)字（二進(jìn)制數(shù)）來表示各個(gè)點(diǎn)的狀態(tài)。這就要求使用狀態(tài)壓縮的對(duì)象的點(diǎn)的狀態(tài)必須只有兩種，0 或 1
我們都知道二進(jìn)制可以用來枚舉子集，例如某個(gè)問題有8種情況，那么我們可以一個(gè)循環(huán)，從0到2^3-1,將所有情況枚舉出來，這里拓展一個(gè)位運(yùn)算的技巧（i>>j&1）: 用來求十進(jìn)制下的數(shù)i第j位是否為1，我們規(guī)定如果當(dāng)前位為1就說明這一位應(yīng)當(dāng)被選中
動(dòng)態(tài)規(guī)劃的問題
狀態(tài)壓縮DP常見問題大概可以分為兩類
1.棋盤式（基于連通性）DP
2.集合式DP
個(gè)人總結(jié)的狀態(tài)壓縮dp三部曲：
-
考慮如何狀態(tài)壓縮
- 確定狀態(tài)表示和狀態(tài)轉(zhuǎn)移方
- 根據(jù)實(shí)際問題確定篩選條件 最關(guān)鍵一步！??！合理情況的篩選一定要考慮完全
解釋一下第三步的原因，我們狀態(tài)壓縮是對(duì)所有情況進(jìn)行枚舉，而實(shí)際的題目中會(huì)有限制，我們根據(jù)題目要求，先對(duì)所有情況進(jìn)行預(yù)處理，用一個(gè)bool數(shù)組，將不合法的數(shù)值標(biāo)記為false即可
例題引入：?P1879 [USACO06NOV]Corn Fields G - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
題意：每一個(gè)是1的都可以種植草地，每個(gè)草地的上下左右不能有草地，求方案數(shù)
第一步：分析如何狀態(tài)壓縮
規(guī)定1表示種植草地，0表示不種值，所以每一行的狀態(tài)由[0,2^m-1]表示，m表示列數(shù)?
第二步：狀態(tài)表示和狀態(tài)轉(zhuǎn)移方程
初狀態(tài) f[0][0] = 1（默認(rèn)一行也不擺也是一種方案）
f[i][j]表示擺完了前i行，第i行的狀態(tài)是j的方案數(shù)
第i行是在前i-1的基礎(chǔ)上加上的所以狀態(tài)轉(zhuǎn)移方程很容易得出：f[i][j] += f[i-1][k];?
第三步： 根據(jù)實(shí)際情況篩選合理情況
本題中要求若中間確定種植草地，則上下左右不允許出現(xiàn)草地，即不允許出現(xiàn)1
我們可以通過位運(yùn)算來確定是否合法
1.行內(nèi)合法 位運(yùn)算技巧： !(i & i >> 1)為真，則為合法情況
技巧講解： i>>1后i-1位來到了i位，i位來到了i+1位的情況，如果i&i>>1等于0不就是說明i-1和i，i和i+1都是不相等的狀態(tài)嗎，也就是我們當(dāng)前第i位是1，那么i-1位和i+1位都是0，就保證了左右沒有草地
2.行間是否合法?
我們假設(shè)第i-1行的狀態(tài)是a,第i行的狀態(tài)是b,那么需要滿足的條件是!(a&b),就是兩行間不能有相鄰的草地，
3.枚舉的狀態(tài)數(shù)是否符合實(shí)際的條件
本題的實(shí)際條件就是不能超過本行的草地?cái)?shù)量
例如一個(gè)3行5列的土地，當(dāng)前行只有兩列是可以種植草地的，所以當(dāng)前土地的草地?cái)?shù)為g[i],那么應(yīng)該滿足a&g[i] = a，就是a應(yīng)該是g[i]的一個(gè)子集，相當(dāng)于a∩g[i] = a
#include<iostream>
using namespace std;
const int mod = 1e9;
int g[14];
int s[1<<14];//s數(shù)組用來存儲(chǔ)狀態(tài)，所以列數(shù)[1,12]，所以可以開到2^14
int f[14][1<<14];f數(shù)組是動(dòng)態(tài)規(guī)劃的數(shù)組，第一維表示行數(shù)，第二維表示當(dāng)前狀態(tài)
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
int x;
cin>>x;
g[i] = (g[i] << 1) + x;//位運(yùn)算
}
}
int cnt = 0;
for(int i = 0;i < (1<<m);i++)
{
if(!(i&i>>1)) s[cnt++] = i;//預(yù)處理，將符合條件的狀態(tài)存下來
}
f[0][0] = 1;//初始
for(int i = 1;i <= n;i++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
if((g[i]&s[a]) == s[a] && !(s[a] &s[b]))//過濾行間和行內(nèi)要滿足的條件
f[i][a] = (f[i-1][b] + f[i][a]) % mod; //狀態(tài)轉(zhuǎn)移
}
}
}
long long ans ;
for(int i = 0;i < cnt;i++) //遍歷所有狀態(tài)，將第n行的合理狀態(tài)加起來
{
ans =(ans + f[n][i]) % mod;
}
cout<<ans;
}最后遍歷所有的合理狀態(tài)也可以根據(jù)狀態(tài)轉(zhuǎn)移方程，第n+1的方案是由第n行轉(zhuǎn)移過來的，
所以f[n+1][0] = （f[n][a1] + f[n][a2] + .....f[n][acnt]）,也就是相當(dāng)于遍歷了一遍，所以我們也可以這樣寫
for(int i = 1;i <= n+1;i++)//循環(huán)到第n+1行
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
if((g[i]&s[a]) == s[a] && !(s[a] &s[b]))
f[i][a] = (f[i-1][b] + f[i][a]) % mod;
}
}
}
cout<<f[n+1][0];例題引入 ：U204941 蒙德里安的夢(mèng)想 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
第一步 首先先給出一個(gè)明顯的結(jié)論：橫放格子的方案數(shù)等于總方案數(shù)
當(dāng)豎放的格子確定好位置后，那么橫放的格子也就確定了，因?yàn)閿[放的方式只有橫放或者豎放，當(dāng)豎放確定后，剩余的坑位也就確定了形狀，顯然這題就是討論哪個(gè)格子是怎么放置的，我們看它給出的數(shù)據(jù)范圍是[1,11]，我們可以考慮按列擺放，那么我們枚舉二進(jìn)制，根據(jù)題目實(shí)際分析應(yīng)該是[0,2^m-1],行數(shù)是n，那么就有n位。
我們可以規(guī)定若某行是1，表示橫，某行為0，表示豎放。
第二步
?用f[i][j]記錄第i列第j個(gè)狀態(tài)。j狀態(tài)位等于1表示上一列有橫放格子，本列有格子捅出來。轉(zhuǎn)移方程很簡單，本列的每一個(gè)狀態(tài)都由上列所有“合法”狀態(tài)轉(zhuǎn)移過來f[i][j] += f[i - 1][k]
初始化條件:f[0][0] = 1第0列只能是狀態(tài)0，無任何格子捅出來。
終止?fàn)顟B(tài)：f[m+1][0]。第m + 1列不能有東西捅出來。
第三步
分析實(shí)際情況：
那么在這個(gè)題中我們應(yīng)該可以想到第i列和第i-1不能為同時(shí)為1，因?yàn)槲覀円?guī)定有1表示當(dāng)前的列是橫放格子的第二個(gè)格子，如果i列為1就說明i-1列應(yīng)該是豎放格子的第一個(gè)
所以條件為!(j&k）為真
第二個(gè)條件：設(shè)當(dāng)前列的狀態(tài)是state，,上一列狀態(tài)為last,我們知道是把行作為狀態(tài)數(shù)，說明這一行有格子，那么我們沒有格子的地方最后是要填滿豎放格子的，豎放格子的高為2，也就是我們兩個(gè)放格子的行之間的行數(shù)應(yīng)該是偶數(shù)個(gè)，如果是奇數(shù)個(gè)不能放下豎放格子，肯定會(huì)有空格，所以state|last 應(yīng)該是不能出現(xiàn)連續(xù)奇數(shù)個(gè)0，這個(gè)條件我們可以通過預(yù)處理，將滿足條件的狀態(tài)存下來,下面通過圖來解釋
綠色為上一列的格子，藍(lán)色表示這一列的格子，last |state 就是兩個(gè)狀態(tài)只要出現(xiàn)1，最后的結(jié)果的這一行就為1，因?yàn)閮蓚€(gè)狀態(tài)的交集在第i列，無論是i-1列的狀態(tài)出現(xiàn)1還是i列出現(xiàn)1，都有第i列肯定有格子，只有兩個(gè)狀態(tài)的當(dāng)前行都為0，第i列的格子才沒有被填，所以我們要找的就是 state|last中是否有連續(xù)的0
?
#include<iostream>
#include<cstring>
using namespace std;
const int N = 13,M = 1<<N;
long long f[N][M];
int cnt;
bool st[M];
int main()
{
int n,m;
while(cin>>n>>m,n||m)
{
memset(f,0,sizeof f);
for(int i = 0;i < (1<<n);i++)
{
cnt = 0;
st[i] = true;
for(int j = 0;j < n;j++)
{
if(i >> j & 1)
{
if(cnt & 1)
{
st[i] = false;
cnt = 0;
}
}
else cnt++;
}
if(cnt & 1) st[i] = false;
}
f[1][0] = 1;//初始條件 第一列不能作為橫放格子的第二個(gè)格子，只有0一種情況
for(int i = 2;i <= m+1;i++)
{
for(int j = 0;j < (1<<n);j++)
{
for(int k = 0;k <(1<<n);k++)
{
if(!(j & k)&& st[j|k]) f[i][j] += f[i-1][k];
}
}
}
cout<<f[m+1][0]<<endl;//第m+1行應(yīng)該是沒有格子的情況
}
}例題引入：P1896 [SCOI2005] 互不侵犯 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
題意很好理解，就是說如果當(dāng)前點(diǎn)放了國王，以它為中心的九宮格都不能放置國王
二：狀態(tài)表示：f[i][j][a]:表示前i行放了j個(gè)國王，第i行狀態(tài)為a的方案數(shù)
狀態(tài)轉(zhuǎn)移：用c數(shù)組存儲(chǔ)當(dāng)前行的為a狀態(tài)時(shí)的國王數(shù)
f[i][j][a] += f[i-1][j-c[k][b];
三.篩選條件：
?1.行內(nèi)合法：與它左右的方格不能同時(shí)放1，!（i&i>>1)為真
2.行間合法：和它的上，左上，右上,下都不能同時(shí)放1，!(a&b),!(a&b>>1),!(a&b<<1)都為真時(shí)，才可以兼容
#include<iostream>
using namespace std;
long long f[14][144][1<<12];
int nums[1<<12];
int s[1<<12];
int n,cnt;
void init()
{
for(int i = 0;i < (1<<n);i++)
{
if(i&(i>>1)) continue;
s[cnt++] = i;
for(int j = 0;j < n;j++)
{
nums[i] += (i>>j&1);//存儲(chǔ)每個(gè)狀態(tài)表示里行間合格的國王數(shù)
}
}
}
int main()
{
int k;
cin>>n>>k;
init();//預(yù)處理行間
f[0][0][0]=1;
for(int i = 1;i <= n+1;i++)//小技巧：遍歷到n+1,那么i+1行的方案數(shù)都由i行轉(zhuǎn)移，所有方案都存儲(chǔ)在i+1行中
{
for(int j = 0;j <= k;j++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
int c = nums[s[b]];
if(j - c >= 0 && !(s[a] & s[b]) && !(s[a] & (s[b]>>1)) && !(s[a]&(s[b]<<1)))
{
f[i][a][j] += f[i-1][b][j-c];
}
}
}
}
}
// cout<<cnt<<endl;
cout<<f[n+1][0][k];
}例題引入?P2704 [NOI2001] 炮兵陣地 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)
這道題和第一題十分相似，但是要求是上下左右各多了一格。
狀態(tài)表示 f[i][a][b] :第i行的狀態(tài)為a，i-1行狀態(tài)為b。
狀態(tài)轉(zhuǎn)移 f[i][a][b] 是由上一行f[i-1][b][c]轉(zhuǎn)移而來。
篩選條件
1.行內(nèi)：!(i&i>>2）和!(i&i>>1)同時(shí)為真
2.行間? a,b,c相與必須為0文章來源：http://www.zghlxwxcb.cn/news/detail-493676.html
3.不能在山地上布署文章來源地址http://www.zghlxwxcb.cn/news/detail-493676.html
#include<iostream>
using namespace std;
int g[110];
int cnt;
int num[1<<10];
int s[1<<10];
int f[2][1<<10][1<<10];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= m;j++)
{
char ch;
cin>>ch;
int x = 0;
if(ch == 'P') x = 1;
g[i] = (g[i]<<1) + x;
}
}
for(int i = 0;i < (1<<m);i++)
{
if(!(i & i >>1)&&!(i & i >>2))
{
s[cnt++] = i;
for(int j = 0;j < m;j++)
{
num[i] += (i >> j & 1);
}
}
}
// cout<<cnt<<endl;
//f[0][0][0] = 1;
for(int i = 1;i <= n +2;i++)
{
for(int a = 0;a < cnt;a++)
{
for(int b = 0;b < cnt;b++)
{
for(int c = 0;c < cnt;c++)
{
if(!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) && (g[i-1]&s[b])==s[b] &&(g[i]&s[a])==s[a])
{
f[i&1][a][b] = max(f[i&1][a][b],f[i-1&1][b][c]+num[s[a]]);
}
}
}
}
}
cout<<f[n+2&1][0][0];
return 0;
}到了這里，關(guān)于一文帶你入門并吃透狀態(tài)壓縮DP的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
