POJ 3254 Corn Fields（状态压缩）

本文主要是介绍POJ 3254 Corn Fields（状态压缩），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一个n*m的田地，每块田地可以种菜，0代表不能种，1可以，求有多少种方法

题解：炮兵布阵系列

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int  M = 1<<13;
#define mod 100000000
int dp[15][M+2];
int map[15][15];
int a[15];
int s[M+2];
int cnt ;
int n,m;
bool ok(int x){if(x&(x<<1)) return false;return true;
}
void init(){cnt = 0;for(int i = 0;i < (1<<m);i++){if(ok(i)) s[cnt++] = i;}
}
bool find(int x,int y){if(x&y) return false;return true;
}
int main(){while(cin >> n >> m){memset(a,0,sizeof(a));for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){cin >> map[i][j];if(!map[i][j]) a[i] |= 1<<j;}}init();memset(dp,0,sizeof(dp));for(int i = 0;i < cnt;i++){if(find(s[i],a[0])) dp[0][i] = 1;}for(int i = 1;i < n;i++){for(int j = 0;j < cnt;j++){if(!find(s[j],a[i])) continue;for(int k = 0;k < cnt;k++){if(!(s[k]&s[j]))dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod;}}}int res = 0;for(int i = 0;i < cnt;i++){res = (res + dp[n-1][i]) % mod;}cout << res << endl;}
}

这篇关于POJ 3254 Corn Fields（状态压缩）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---