状态压缩DP
该题和之前的状态压缩DP不一样的点在于,部分区域不能放。
因为我们用二进制表示放置的状态,放为1,不放为0,所以将每层不能放的置为1,表明这里开始就已经种植了玉米,在后面状态转移方程的时候,与每层的状态作
&
运算判断合法性,即当前的状态和初始状态不能重复。即当前状态放置的不能和初始化的已经放置有重复。
时间复杂度$O(N2^M)$,空间复杂度$O(2^M)$
AC代码
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 14, M = 1 << N, MOD = 1e8;
int n, m;
int g[N]; //g[i]表示每层初始化的状态,把不能种植的土地看成已经种植的土地
vector<int> valid;
vector<int> st[M];
int f[N][M];
//判断s状态是否合法,即s二进制是否不存在有连续两个1
bool check(int s) {
for (int i = 0 ; i < m ; i ++) {
if ((s >> i) & 1 && (s >> (i + 1)) & 1)
return false;
}
return true;
}
int main() {
//读入
cin >> n >> m;
for (int i = 0 ; i < n ; i ++) {
int s = 0;
for (int j = m - 1 ; j >= 0 ; j --) {
int t;
cin >> t;
if (!t) s |= (1 << j);
}
g[i] = s;
}
//初始化所有合法的状态
for (int i = 0 ; i < 1 << m ; i ++)
if (check(i))
valid.push_back(i);
//初始化a状态,能被哪些b状态转移到
for (int i = 0 ; i < valid.size() ; i ++) {
for (int j = 0 ; j < valid.size() ; j ++) {
int a = valid[i], b = valid[j];
if ((a & b) == 0)
st[a].push_back(b);
}
}
//状态压缩DP
f[0][0] = 1;
for (int i = 1 ; i <= n + 1 ; i ++) {
int s = g[i - 1];
for (int j = 0 ; j < valid.size() ; j ++) {
if (!(s & valid[j])) {
for (int u = 0 ; u < st[valid[j]].size() ; u ++) {
int a = valid[j], b = st[a][u];
f[i][a] = (f[i][a] + f[i - 1][b]) % MOD;
}
}
}
}
cout << f[n + 1][0];
return 0;
}