题目链接
https://www.luogu.org/problemnew/show/P1879
分析
一类状压DP套路,将每一行视为一个阶段,通过状态可行性来由一行更新到另一行
那么我们先预处理出所有状态本身是否合法(即有没有相邻的两块草地)。如果第$i$行状态为$x$,第$i+1$行为$y$,那么显然x&y为0时,这两行才是合法的。同时若题目给出的第$i$行田地的状态为$s$,那么$x|s==s$时这一行才是合法的
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cctype> #include <iostream> #include <queue> #define ll long long #define ri register int using std::min; using std::max; template <class T>inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x;return ; } const int maxn=10005; const int inf=0x7fffffff; const int p=100000000; int f[1<<12][13]; bool ok[1<<12]; int ban[13]; int n,m,sz; int main(){ int cnt=0,ppp=0,x,y; read(n),read(m); for(ri i=1;i<=n;i++){ x=0,y=0; for(ri j=1;j<=m;j++){ read(x); y=y*2+x; } ban[i]=y; } ban[0]=sz-1; sz=1<<m; for(ri i=0;i<sz;i++){ cnt=0,ppp=0; for(ri j=0;j<m;j++){ if(i&(1<<j))cnt++; else{ if(cnt>1)ppp=1; cnt=0; } } if(cnt>1)ppp=1; ok[i]=ppp; } f[0][0]=1; for(ri k=1;k<=n;k++){ for(ri i=0;i<sz;i++) if(!ok[i]&&(i|ban[k])==ban[k]) for(ri j=0;j<sz;j++){ if(!(i&j)&&!ok[j]&&(j|ban[k-1])==ban[k-1]){ f[i][k]+=f[j][k-1]; if(f[i][k]>p)f[i][k]%=p; } } } ll ans=0; for(ri i=0;i<sz;i++)ans=(ans+f[i][n])%p; printf("%lld\n",ans); return 0; }
|