#include <iostream>
#include <cmath>
using namespace std;

int dp[60][60][102];
int len = 0,n,m,st[1024];
char map[110][15];

bool ok(int x)
{
	if (x < 0 || x >= m)
		return false;
	return true;
}

int f(int x, int y, int n) //x为行n的炮状态，y为行n-1的炮状态
{
	if (dp[x][y][n] != -1)
		return dp[x][y][n];
	int max = 0;
	int s = 0;
	for (int i = 0; i < m; ++i)
		if ((st[x]&(1<<i)) != 0)
			++s;
	if (n == 1)
	{
		dp[x][y][n] = s;
		return s;
	}
	int temp = st[x]|st[y];
	for (int i = 0; i < len; ++i)
	{
		bool b = true;
		int sum = 0;
		if ( (temp&st[i]) != 0)
			continue;
		for (int j = 0; j < m; ++j)
		{
			if (map[n-2][j] == 'H' && (st[i]&(1<<j)) != 0)
			{
				b = false;
				break;
			}
		}
		if (b)
		{
			int tt = f(y,i,n-1);
			max = max > tt ? max : tt;
		}
	}
	max += s;
	dp[x][y][n] = max;
	return max;
}
int main()
{

	scanf("%d %d",&n,&m);
	int status = (int)pow(2.0,m); //此处是计算出有最多有多少种炮的放法

	//处理每行的所有情况，用位处理，而后存储到st数组中
	for (int i = 0; i < status; ++i)
	{
		bool b = false;
		for (int j = 0; j < m; ++j)
		{
			if ((i&(1<<j)) != 0)
			{
				if (ok(j-1) && (i&(1<<(j-1))) != 0)
				{
					b = true;
					break;
				}
				if (ok(j-2) && (i&(1<<(j-2))) != 0)
				{
					b = true;
					break;
				}
				if (ok(j+1) && (i&(1<<(j+1))) != 0)
				{
					b = true;
					break;
				}
				if (ok(j+2) && (i&(1<<(j+2))) != 0)
				{
					b = true;
					break;
				}
			}
		}
		if (!b)
			st[len++] = i;
	}

	//先初始化下map的第0行，全是山
	for ( int i = 0; i < m; ++i )
	{
		map[0][i] = 'H';
	}

	//输入map
	for (int i = 1; i <= n; ++i)
		scanf("%s", map[i]);

	//初始化数组dp
	for ( int i = 0; i < 60; ++i )
	{
		for ( int j = 0; j < 60; ++j )
		{
			for ( int k = 0; k < 102; ++k )
			{
				dp[i][j][k] = -1;
			}
		}
	}

	//dp
	int max = 0;
	for (int i = 0; i < len; ++i)
		for (int j = 0; j < len; ++j)
		{
			bool b = true;
			if ((st[i]&st[j]) != 0)
				continue;
			for (int k = 0; k < m; ++k)
			{
				if (map[n][k] == 'H' && (st[i]&(1<<k)) != 0)
				{
					b = false;
					break;
				}
				if (map[n-1][k] == 'H' && (st[j]&(1<<k)) != 0)
				{
					b = true;
					break;
				}
			}
			if (b)
			{
				int tt = f(i,j,n);
				max = max > tt ? max : tt;
			}
		}
		printf("%d\n",max);
		return 0;
}

• 试试这个？ (53) majia8 2009-05-06 08:53:17
  • 顶这两个数据！！！ (44) ccsu2008021220 2009-09-18 15:24:08
    • Re:顶这两个数据！！！ (48) salvete 2018-10-24 21:02:26
  • Re:试试这个？ (113) sliverwxj 2010-06-18 12:38:37
    • Re:试试这个？ (45) haha132 2013-08-09 09:23:49
  • Re:试试这个？ (80) mutou3221 2011-03-02 21:35:20
  • Re:试试这个？ (67) haha132 2013-08-09 08:59:21
    • Re:试试这个？ (45) haha132 2013-08-09 09:22:44
  • 大牛啊，一下点醒WA中人 (5) 1507030329 2016-05-09 16:28:56
  • Re:试试这个？ (5) phython 2017-03-08 11:24:55
  • n和m均为1的数据坑死人啊 (0) wumingshi999 2017-04-01 16:00:20
  • 666，瞬间AC！ (2) 201716080213 2018-09-03 21:45:58
• Re:这个题有什么很变态的测试数据吗？老是过不了。附代码，希望大牛们帮忙，谢谢1 (9) wangzhili 2014-04-26 16:14:52
  • Re:这个题有什么很变态的测试数据吗？老是过不了。附代码，希望大牛们帮忙，谢谢1 (11) wangzhili 2014-04-26 16:15:27
    • Re:这个题有什么很变态的测试数据吗？老是过不了。附代码，希望大牛们帮忙，谢谢1 (8) 674019130 2017-04-22 21:03:28