前言

水解警告，数据水勉强卡过的

---

正题

---

题目大意

$n\ast m$的网格里面有些格子被禁止，现在求选取若干个不相邻的格子的方案数。

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

---

解题思路

听说是插头$dp$然后想了一下觉得比插头$dp$的模板简单多了。

如果这个轮廓线外侧有玉米就相当于有一个插头，然后发现右插头一定和刚刚那个格子的下插头相等，所以只需要存储下插头的状态就好了。

然后暴力搜出所有合法状态（注意因为轮廓线下凸的地方可以有两个相邻的$1$，所以只有一个位置有两个相邻格子的状态也算合法状态），只有$129267$个。

然后因为状态大小的上限$2^m$，所以可以直接暴力用一个数组来记录状态，不用挂表了。

然后转移也很好写。

所以写起来很舒服但是这样不吸氧跑的很慢。（时间复杂度换代码复杂度！）

QuantAsk在玉米田++吸氧，这是他的代码运行时间发生的变化

但是其实看了一下正解的写法，还有一个优化就是记下第一个相邻$1$的插头位置然后挂表，然后对于每个位置只考虑在轮廓线下凸位置有相邻$1$的状态，好像会快很多，状态也少很多。

---

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); }

总结

以上是生活随笔为你收集整理的玉米田(加加强版)【插头dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。