P2704 [NOI2001] 炮兵阵地(状压dp)

[NOI2001] 炮兵阵地 - 洛谷https://www.luogu.com.cn/problem/P2704今天又是学习状压dp的一天！

这题的数据范围很明显可以用状压dp来写，上手就应该想到dp数组中有两维是第i行和第i行的状态，但炮兵的影响有两行，所以还要记录上一行的状态。

可以先把每一行可行的方案数求出来再枚举，可以节省点时间，有些题可能会卡掉。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;


int n, m;
int a[MAXN];
int dp[(1 << 10)][(1 << 10)][105];
int cnt;
int rec[MAXN];
int sum[MAXN];
int getsum(int x) {
	int tot = 0;
	while (x)
		tot++, x -= lowbit(x);
	return tot;
}

int main() {
	char ch;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf(" %c", &ch);
			a[i] <<= 1;
			a[i] += ((ch == 'H') ? 1 : 0);
		}
	}
	rec[++cnt] = 0;
	for (int i = 1; i < (1 << m); i++) {
		if (i & (i << 1))
			continue;
		if (i & (i << 2))
			continue;
		rec[++cnt] = i;
	}
	for (int i = 1; i <= cnt; i++) {
		sum[i] = getsum(rec[i]);
	}
	for (int i = 1; i <= cnt; i++) {
		if (rec[i]&a[1])
			continue;
		dp[0][rec[i]][1] = sum[i];
	}
	for (int i = 1; i <= cnt; i++) {
		if (rec[i]&a[2])
			continue;
		for (int j = 1; j <= cnt; j++) {
			if (rec[i]&rec[j] || rec[j]&a[1])
				continue;
			dp[rec[j]][rec[i]][2] = sum[i] + sum[j];
		}
	}
	for (int i = 3; i <= n; i++) {
		for (int j = 1; j <= cnt; j++) {
			if (rec[j]&a[i])
				continue;
			for (int k = 1; k <= cnt; k++) {
				if (rec[k]&rec[j] || rec[k]&a[i - 1])
					continue;
				for (int p = 1; p <= cnt; p++) {
					if (rec[p]&rec[k]||rec[p]&rec[j] || rec[p]&a[i - 2])
						continue;
					dp[rec[k]][rec[j]][i] = max(dp[rec[k]][rec[j]][i], dp[rec[p]][rec[k]][i - 1] + sum[j]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= cnt; i++) {
		if (rec[i]&a[n])
			continue;
		for (int j = 1; j <= cnt; j++) {
			if (rec[i]&rec[j] || rec[j]&a[n - 1])
				continue;
			ans = max(ans, dp[rec[j]][rec[i]][n]);
		}
	}
	printf("%d", ans);
	return 0;
}