玉米田【状压DP】【记搜】

本文主要是介绍玉米田【状压DP】【记搜】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

一个$n\times m$的矩阵里，有几个是可以种植玉米的。求玉米种植不相连的方案数。

---

思路：

DFS爆搜 只 能拿90分，正解是状压DP。
可以把可种植玉米的土地用1表示，贫瘠的土地用0表示，每一行串成的数字就是一个二进制数，状态压缩后，就成了一个较小的十进制数。
设$f[i][j]$表示在第$i$行，状态压缩后的十进制数为$j$的情况下，总共种植的方案数。那么，若$k$&$j=j$，那么说明在上一行的种植情况为$k$时，这一行种植情况为$j$是合法的（即没有两个玉米种植位置相连）。那么$f[i][j]$就与$f[i-1][k]$可以成立，$f[i][j]+=f[i-1][k]$。
最终答案就是$\sum^{2^m-1}_{i=0}f[n][i]$。

---

代码：

#include <cstdio>
#include <iostream>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;int n,m,a[21][21],g[21],f[21][5001],ms,num[41],sum;
bool state[5001];int main()
{fre(cowfood);scanf("%d%d",&n,&m);num[1]=1;for (int i=2;i<=30;i++)num[i]=num[i-1]*2;  //为下面求2^i初始化for (int i=1;i<=n;i++)for (int j=1;j<=m;j++){scanf("%d",&a[i][j]);g[i]=g[i]+num[j]*a[i][j];  //状态压缩}ms=num[m+1];  //2^mfor (int i=0;i<ms;i++)state[i]=((!((i<<1)&i))&&(!((i>>1)&i)));  //初始化f[0][0]=1;for (int i=1;i<=n;i++)for (int j=0;j<ms;j++)if (state[j]&&((j&g[i])==j))  //为j的情况合法for (int k=0;k<ms;k++)if (!(j&k))  //k在上一行的情况合法f[i][j]+=f[i-1][k];for (int j=0;j<ms;j++)sum=(sum+f[n][j])%100000000;return printf("%d\n",sum)&0;
}

这篇关于玉米田【状压DP】【记搜】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---