2259.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2259 on 2006-05-29 at 10:20:48 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 128, M = 5;
const int BSN = 1 << 15, LSN = 1 << 5;
const int NINF = - 1 << 28;

int map[M][N], n, m;
bool fbd[BSN];

int select(int, int);

int main()
{
	int p, i, j, k, t, T;
	int num[N][LSN][LSN];
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d %d", &n, &m, &p);
		for(i = 0; i < m; i++)
			for(j = 0; j < n; j++) scanf("%d", &map[i][j]);
		memset(fbd, false, sizeof(fbd));
		for(i = 0; i < p; i++) {
			int st = 0;
			for(j = 0; j < m; j++)
				for(k = 0; k < 3; k++) {
					int e; scanf("%d", &e);
					st |= e << (k*m+j);
				}
			fbd[st] = true;
		}
		int tms = 1 << (2*m), ms = 1 << m;
		for(i = 0; i < tms; i++) {
			int l = i >> m, h = i & (ms-1);
			num[1][l][h] = select(0, l) + select(1, h);
		}
		for(i = 2; i < n; i++)
			for(j = 0; j < tms; j++) {
				int mid = j >> m, h = j & (ms-1), score = select(i, h), l;
				num[i][mid][h] = NINF;
				for(l = 0; l < ms; l++) {
					int squ = (h<<(2*m)) | (mid<<m) | l;
					if(!fbd[squ]) num[i][mid][h] = max(num[i][mid][h], num[i-1][l][mid]+score);
				}
			}
		int best = NINF;
		for(i = 0; i < tms; i++) best = max(best, num[n-1][i>>m][i&(ms-1)]);
		printf("%d\n", best);
	}
	
	return 0;
}

int select(int c, int st)
{
	int total = 0, i;
	for(i = 0; i < m; i++)
		if(st&(1<<i)) total += map[i][c];
	return total;
}