禁食后人(如果你100pts 但 hack 没过)
查看原帖
禁食后人(如果你100pts 但 hack 没过)
982513
EternalHeart1314楼主2024/8/18 21:05

n=1 or 2n = 1\ or\ 2.

可以加上:

n += 2, a[n - 1] = a[n] = s - 1;

即在最下面加上两座“长城”,这样 nn 就大于等于 33 了。

参考代码:

#include <bits/stdc++.h>
using namespace std;

const int N = (1 << 10) + 7;
int n, m, s, ans, a[N], c[N], f[3][N][N];
char ch;

main() {
	cin >> n >> m, s = (1 << m);
	for (int i = 1; i <= n; ++i) for (int j = 0; j < m; ++j)
		cin >> ch, a[i] |= (ch == 'H') << j;
	for (int i = 0; i < s; ++i) c[i] = __builtin_popcount(i);
	for (int i = 0; i < s; ++i) if (!(i & a[1] | i & (i << 1 | i << 2)))
		for (int j = 0; j < s; ++j) if (!(i & j | j & a[2] | j & (j << 1 | j << 2)))
			f[0][i][j] = c[i] + c[j];
	n += 2, a[n - 1] = a[n] = s - 1;
	for (int i = 3; i <= n; ++i) for (int j = 0; j < s; ++j)
		if (!(j & a[i - 1] | j & (j << 1 | j << 2))) for (int k = 0; k < s; ++k)
			if (!(k & a[i] | k & (k << 1 | k << 2) | k & j)) for (int l = 0; l < s; ++l)
				if (!(l & a[i - 2] | l & (l << 1 | l << 2) | l & j | l & k))
					f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][l][j] + c[k]);
	for (int i = 0; i < s; ++i) for (int j = 0; j < s; ++j) ans = max(ans, f[n & 1][i][j]);
	return cout << ans, 0;
}//f[i][j][k] = 前 i 行中,第 i 行状态为 j,第 i - 1 行状态为 k 的答案 
2024/8/18 21:05
加载中...