多年不更博客，本来弱到要被淘汰了，突然又想坚持了
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <map> using namespace std; const int maxn=(1<<13); const int mod=1e8; int dp[20][maxn]; int a[maxn]; int mapp[20]; int n,m; int cnt; void init() { cnt=0; for(int i=0;i<(1<<m);i++) { if(!((i<<1)&i)) a[cnt++]=i;//将不存在相邻草地的状况存一下 } } int main() { scanf("%d%d",&n,&m); init(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x; scanf("%d",&x); if(!x) mapp[i]+=(1<<(m-j));//肥沃为0，不肥沃为1，方便&a取非为合法情况 } } for(int i=0;i<cnt;i++) { if(!(a[i]&mapp[1])) { dp[1][i]=1;//合法 } } for(int i=2;i<=n;i++) for(int j=0;j<cnt;j++) if(!(a[j]&mapp[i])) { for(int k=0;k<cnt;k++) if(!(a[k]&mapp[i-1]))//上一行的合法情况 { if(!(a[j]&a[k]))//保证两行合法情况在列上不相切 dp[i][j]=(dp[i][j]+dp[i-1][k])%mod; } } int ans=0; for(int i=0;i<cnt;i++) ans=(ans+dp[n][i])%mod; printf("%d\n",ans); return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/9106195.html
相关资源：数据结构—成绩单生成器