前言

水解警告，數(shù)據(jù)水勉強(qiáng)卡過的

---

正題

---

題目大意

$n?m$的網(wǎng)格里面有些格子被禁止，現(xiàn)在求選取若干個(gè)不相鄰的格子的方案數(shù)。

$1\le n\le 120,1\le m\le 21$

---

解題思路

聽說是插頭$dp$然后想了一下覺得比插頭$dp$的模板簡單多了。

如果這個(gè)輪廓線外側(cè)有玉米就相當(dāng)于有一個(gè)插頭，然后發(fā)現(xiàn)右插頭一定和剛剛那個(gè)格子的下插頭相等，所以只需要存儲下插頭的狀態(tài)就好了。

然后暴力搜出所有合法狀態(tài)（注意因?yàn)檩喞€下凸的地方可以有兩個(gè)相鄰的$1$，所以只有一個(gè)位置有兩個(gè)相鄰格子的狀態(tài)也算合法狀態(tài)），只有$129267$個(gè)。

然后因?yàn)闋顟B(tài)大小的上限$2^m$，所以可以直接暴力用一個(gè)數(shù)組來記錄狀態(tài)，不用掛表了。

然后轉(zhuǎn)移也很好寫。

所以寫起來很舒服但是這樣不吸氧跑的很慢。（時(shí)間復(fù)雜度換代碼復(fù)雜度！）

QuantAsk在玉米田++吸氧，這是他的代碼運(yùn)行時(shí)間發(fā)生的變化

但是其實(shí)看了一下正解的寫法，還有一個(gè)優(yōu)化就是記下第一個(gè)相鄰$1$的插頭位置然后掛表，然后對于每個(gè)位置只考慮在輪廓線下凸位置有相鄰$1$的狀態(tài)，好像會快很多，狀態(tài)也少很多。

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define adt(x,y) ((x+y>=P)?x+y-P:x+y) using namespace std; const int P=1e8; int n,m,o,cnt,p,ans,v[200],t[2],mark[2][129268],s[2][129268],f[2][129268],S[1<<21]; void Add(int z,int v){int x=S[z];if(mark[o][x]!=p){f[o][x]=v;s[o][++t[o]]=z;mark[o][x]=p;return;}f[o][x]=adt(f[o][x],v);return; } int main() {freopen("cowfood.in","r",stdin);freopen("cowfood.out","w",stdout);scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0,x;j<m;j++)scanf("%d",&x),v[i]|=((!x)<<j);}++p;for(int i=0;i<1<<m;i++){int flag=0;for(int j=1;j<m;j++)if(((i>>j)&1)&&((i>>j-1)&1))flag++;if(flag<2){++cnt,S[i]=cnt;if(flag<1&&!(i&v[0])){f[o][cnt]=1;mark[o][cnt]=p;s[o][++t[o]]=i;}}}int z,w;for(int i=1;i<n;i++)for(int j=0;j<m;j++){++p;o=!o;t[o]=0;for(register int k=1;k<=t[!o];k++){z=s[!o][k];w=f[!o][S[z]];if((z>>j)&1)Add(z^(1<<j),w);else if((j>0&&((z>>j-1)&1))||((v[i]>>j)&1))Add(z,w);else Add(z,w),Add(z|(1<<j),w);}}for(int k=1;k<=t[o];k++)ans=adt(ans,f[o][S[s[o][k]]]);printf("%d\n",ans); }

總結(jié)

以上是生活随笔為你收集整理的玉米田(加加强版)【插头dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。