题目链接: https://www.luogu.org/problemnew/lists?name=1879
- Code:
- //2018-09-17 提高 +
- // 状压 dp
- #include<iostream>
- #include<cstdio>
- #define mod 100000000
- using namespace std;
- long long n,m,ans;
- int map[13][13];
- long long f[1<<12][13];
- int y[13],sign[1<<12];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- scanf("%d",&map[i][j]);
- // 记录土地情况
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- y[i]=(y[i]<<1)+map[i][j];
- // 合并土地情况
- // 方便后面判断
- // 枚举每一种状态
- // 预处理左右不行的状态
- for(int i=0;i<(1<<m);i++)
- {
- if(!(i&(i<<1)) && !(i&(i>>1)))
- {
- sign[i]=1;
- // 标记
- if((i&y[1]) == i) f[i][1]=1;
- // 如果这种状态符合土地条件
- // 初始化 f 数组
- }
- }
- for(int i=2;i<=n;i++)
- // 枚举每一行
- for(int j=0;j<(1<<m);j++)
- // 枚举上一行的状态
- if(((j&y[i-1])==j) && sign[j])
- // 如果土地肥沃, 且当前状态左右不冲突
- for(int k=0;k<(1<<m);k++)
- // 枚举这一行的状态
- if(((k&y[i])==k)&&!(j&k)&&sign[k])
- f[k][i]=(f[k][i]+f[j][i-1])%mod;
- // 当前行的状态只会收上一行的影响
- for(int i=0;i<(1<<m);i++) ans=(ans+f[i][n])%mod;
- // 记录答案
- cout<<ans;
- return 0;
- }
- //By Yfengzi
来源: http://www.bubuko.com/infodetail-2776576.html