滚动数组真是化腐朽为神奇。
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1 << 11;
int dp[2][M][M];
vector<int> v1; //存合法状态
vector<int> v2[M];//存可合法转移的状态
int n, m;
char ch;
int arr[N], w[M];
//求二进制中1的个数
int count(int u) {
int ret = 0;
for (int i = 0; i < 20; i++) ret += u >> i & 1;
return ret;
}
//判断当前序列是否满足条件
bool check(int u) { return !((u >> 1 & u) || (u >> 2 & u)); }
//判断当前状态是否不能放在第i行中
bool right(int u, int i) {
if (i <= 0) return 0;
return (arr[i] | u) > arr[i];
}
int main() {
//输入
cin >> n >> m;
//处理地图,化为二进制数字
for (int i = 1; i <= n; i++) {
int ret = 0;
for (int j = 1; j <= m; j++) {
cin >> ch;
ret = ret * 2 + (ch == 'P');
}
arr[i] = ret;
}
//找出所有合法状态
m = 1 << m;
for (int i = 0; i < m; i++) {
if (check(i)) {
v1.push_back(i);
w[i] = count(i);
}
}
//找出所有可合法转移的状态
for (auto e1 : v1) {
for (auto e2 : v1) {
if (!(e1 & e2)) {
v2[e1].push_back(e2);
}
}
}
//判断是否满足条件(可以放在地图中 且 e1 e2 e3互不冲突)
for (int i = 1; i <= n; i++) {
for (auto e1 : v1) {
if (right(e1, i)) continue;
for (auto e2 : v2[e1]) {
if (right(e2, i - 1)) continue;
for (auto e3 : v2[e2]) {
if (right(e3, i - 2)) continue;
if ((e1 & e3)) continue;
dp[i & 1][e1][e2] = max(dp[i & 1][e1][e2], dp[!(i & 1)][e2][e3] + w[e1]);
}
}
}
}
//输出最大值
int ret = 0;
for (auto e1 : v1) {
if (right(e1, n)) continue;
for (auto e2 : v2[e1]) {
if (right(e2, n - 1)) continue;
ret = max(ret, dp[n & 1][e1][e2]);
}
}
cout << ret << endl;
//结束
return 0;
}