http://acm.hdu.edu.cn/showproblem.php?pid=4539

main.cpp

#include <cstdio>
#include <cstring>
#include <vector>

typedef unsigned int st;

int n, m;
st a[1000];
st valid1[1030];
int validCnt[1030];
int f[2][1030][1030];
int valid1N;

int max(int a, int b) {
	if (a < b) {
		return b;
	}
	return a;
}

bool validA(int i, st k) {
	if (0 <= i && i < n) {
		return ((~a[i]) & k) == 0;
	}
	return true;
}

bool isValid2(st a, st b) {
	return (a & b) == 0;
}

bool isValid1(st a, st b) {
	return isValid2((a >> 1), b) && isValid2(a, (b >> 1));
}

bool isValid0(st a) {
	return (((a >> 2) & a) == 0) && (((a << 2) & a) == 0);
}

int main() {
	while (scanf("%d%d", &n, &m) == 2) {
		for (int i = 0; i < n; i++) {
			st temp = 0;
			for (int j = 0; j < m; j++) {
				int bit;
				scanf("%d", &bit);
				temp = (temp << 1) + bit;
			}
			a[i] = temp;
		}
		valid1N = 0;
		for (st i = 0; i < (1ul << m); i++) {
			if (isValid0(i)) {
				valid1[valid1N] = i;
				int temp = 0;
				st t = i;
				while (t > 0) {
					if (t & 1) {
						temp++;
					}
					t >>= 1;
				}
				validCnt[i] = temp;
				valid1N++;
			}
		}

		int p = 1;
		memset(f[0], 0, sizeof(f[0]));
		for (int i = 0; i < n; i++) {
			memset(f[p], 0, sizeof(f[p]));
			for (int jx = 0; jx < valid1N; jx++) {
				st j = valid1[jx];
				if (!validA(i - 2, j)) {
					continue;
				}
				for (int kx = 0; kx < valid1N; kx++) {
					st k = valid1[kx];
					if (!validA(i - 1, k)) {
						continue;
					}
					for (int kkx = 0; kkx < valid1N; kkx++) {
						st kk = valid1[kkx];
						if (!validA(i, kk)) {
							continue;
						}
						if (isValid2(j, kk) && isValid1(k, kk)) {
							f[p][k][kk] = max(f[p][k][kk], validCnt[kk] + f[1 - p][j][k]);
						}
					}
				}
			}
			p = 1 - p;
		}
		int ans = 0;
		p = 1 - p;
		for (int i = 0; i < valid1N; i++) {
			for (int j = 0; j < valid1N; j++) {
				ans = max(ans, f[p][valid1[i]][valid1[j]]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}