Dynamic Programming with State Compression POJ 1185 炮兵阵地

DP_ChessAttack.cc

#include <cstdio>
#include <cstring>
#include <algorithm>

#define maxn		100
#define maxm		10
#define maxstatus	70

using namespace std;

int total_status;

int f[2][maxstatus][maxstatus];

int map[maxn];

int status[maxstatus];

int ones[maxstatus];

int n, m;

inline bool check(int status)
{
	if (status & (status << 2)) return false;
	if (status & (status << 1)) return false;
	return true;
}

inline int binary_number_of_one(int x)
{
	int counter;
	for (counter = 0; x; ++ counter)
		x &= x - 1;
	return counter;
}

void find_all_status()
{
	int size = 1 << m;
	total_status = 0;
	for (int i = 0 ; i < size; ++ i)
	{
		if (check(i))
		{
			status[total_status] = i;
			ones[total_status] = binary_number_of_one(i);
			++ total_status;
		}
	}
	
}


int main()
{
	char s[20];
	while (scanf("%d%d", &n, &m) != EOF)
	{
		for (int i = 0; i < n; ++ i)
		{
			scanf("%s", s);
			map[i] = 0;
			for (int j = 0; j < m; ++ j)
			{
				if (s[j] == 'H')
					map[i] = (map[i] << 1) | 1;
				else
					map[i] = map[i] << 1;
			}
		}
		
		find_all_status();

		memset(f[0], -1, sizeof(f[0]));
		for (int i = 0 ; i < total_status; ++ i)
			if ((map[0] & status[i]) == 0)
				f[0][i][0] = ones[i];

		for (int i = 1; i < n; ++ i)
		{
			memset(f[i & 1], -1, sizeof(f[i & 1]));
			for (int j = 0; j < total_status; ++ j)
				if ((status[j] & map[i]) == 0)
				{
					for (int k = 0; k < total_status; ++ k)
					{
						if ((status[j] & status[k]) == 0)
						{
							for (int l = 0; l < total_status; ++ l)
								if ((status[j] & status[l]) == 0 && f[(i - 1) & 1][k][l] != -1)
									f[i & 1][j][k] = max(f[i & 1][j][k], f[(i - 1) & 1][k][l] + ones[j]);
						}
					}
				}
		}

		int ans = 0;
		if (n != 0)
		{
			for (int i = 0; i < total_status; ++ i)
				for (int j = 0; j < total_status; ++ j)
					ans = max(ans, f[(n - 1) & 1][i][j]);
		}
		printf("%d\n", ans);
	}

	return 0;
}

orz