状压贪心dfs

int dfs(int pos, int used, int mask) {
	if (pos == 20) {
		int else_cnt = n - used, sum = 0;
		for (int i = 0; i < 20; i ++)
			cnt[i] = pc[mask & g[i]];
		sort(cnt, cnt + 20, greater<int>());
		for (int i = 0; i < else_cnt; i ++)
			sum += cnt[i];
		return sum;
	}
	if (used >= n) return -114514;
	int sum = dfs(pos + 1, used, mask << 1);
	if (flag[pos + 1]) sum = max(sum, dfs(pos + 1, used + 1, mask << 1 | 1));
	return sum;
}
int main() {
	cin >> n;
	for (int i = 0; i < 20; i ++)
		for (int j = 0; j < 20; j ++) {
			cin >> s[i][j], g[i] <<= 1;
			if (s[i][j] == '#') g[i] ++, flag[j] = true;
		}
	for (int i = 0; i < 1 << 20; i ++)
		pc[i] = popcount(i);
	cout << dfs(0, 0, 0) << '\n';
	return 0;
}

状压贪心， $50\text{pts}$

满分状压改 $\text{dfs}$ ，这里限于篇幅，不放了。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, ans, cnt[N];
char s[N][N];
int popcount(int S) {
	int res = 0;
	do if (S & 1) res ++; while(S >>= 1);
	return res;
}
int main() {
	cin >> n;
	for (int i = 0; i < 20; i ++)
		for (int j = 0; j < 20; j ++)
			cin >> s[i][j];
	for (int i = 0; i < 1 << 20; i ++) {
		int used = popcount(i), else_cnt = n - used, sum = 0;
		if (used >= n) continue;
		memset(cnt, 0, sizeof cnt);
		for (int j = 0; j < 20; j ++) {
			if (i & 1 << j)
				for (int k = 0; k < 20; k ++)
					if (s[k][j] == '#') cnt[k] ++;
		}
		sort(cnt, cnt + 20, greater<int>());
		for (int i = 0; i < else_cnt; i ++)
			sum += cnt[i];
		ans = max(ans, sum);
	}
	cout << ans << '\n';
	return 0;
}