Luogu P1879 [USACO06NOV]Corn Fields G 题解

yzxoi

发布于 2022-09-19 12:46:08

4100

发布于 2022-09-19 12:46:08

文章被收录于专栏：OI

Luogu P1879 [USACO06NOV]Corn Fields G 题解

Describe

题目链接

给一个M\times N的矩阵，矩阵每个位置为0/1，问选一些1使这些不相邻的方案数。

Solution

明显状压DP。

那么怎么DP呢？

设f[i][j]表示第i行状态为j的方案数。

那么转移就可以暴力枚举上一行的状态再判断可能性转移。

f[i][j]+=f[i-1][k]

那么怎么判断是否可行呢？

!j\&(j<<1)\&\&!j\&(j>>1)

直观感受

那么还有什么条件呢？S[i]\&j\text{^}j1。!j\&k

那么就直接上代码（逃：

Code

#include<bits/stdc++.h>
#define mod 100000000
using namespace std;
int m,n,S[20],f[20][(1<<13)+10],ans;
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int x,j=1;j<=n;j++)
cin>>x,S[i]=S[i]<<1x;//整合一行信息
f[0][0]=1;//初始化
for(int i=1;i<=m;i++){
for(int j=0;j<(1<<n);j++){
if(j&(j<<1)j&(j>>1)S[i]&j^j) continue ;//判断三个条件
for(int k=0;k<(1<<n);k++){
if(k&j) continue ;//和上一行有冲突
f[i][j]+=f[i-1][k];//累计
f[i][j]%=mod;
}
}
}
for(int i=0;i<(1<<n);i++) ans+=f[m][i],ans%=mod;//总和
cout<<ans<<endl;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-04-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除