POJ 1185 炮兵阵地（状压dp）（棋盘dp）

这题和poj 3254很像，但是更复杂了一些

都属于棋盘里放东西，然后又各种各样的限制，然后求方案或者最大值

（1）上一道题距离要大于1，这道题是大于2。所以判断的时候变成

!(x & (x << 1) || (x & x << 2))

然后关于有效状态数，可以自己输入最大的数据，例如这道题就是n=10，然后输出状态数，就可以得到等于60

（2）这道题涉及到前两行的状态。一开始觉得这道题应该是和上一道题是一样的，设第几行和状态是什么就好了

但是这样的话就不能涉及到上上行的状态。因此状态要涉及到这一行和上一行，为什么不顺便把上上行也加进来呢？因为更新的时候用到i-1是可以多往上一行的。同理，如果是往上n行，就要在状态设计中有当前这一行和往上n-2行的状态。

（3）这道题求的是最大值。那么不一定是放到最后一行的答案。所以就要把所有情况都遍历一遍求答案。

（4）还有题目输入的时候，如果是H，就要标记把这一位标记为1，如果下标从0开始的话，就可以写为1 << (m - j - 1)

但是我发现直接写1 << j也可以，因为这样只是把图左右翻过来了而已，这道题只是求最大值，不是求具体的方案，所以对答案并不会有任何影响。

#include<cstdio>

#include<vector>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 112;

const int MAXM = 70;

int dp[MAXN][MAXM][MAXM], map[MAXN];

int num[MAXM], n, m;

vector<int> state;

int one(int x) { return !x ? 0 : 1 + one(x & (x - 1)); }

int main()

{

	scanf("%d%d", &n, &m);

	REP(x, 0, 1 << m)

	  if(!(x & (x << 1) || (x & x << 2)))

	  {

	  	  state.push_back(x);

	  	  num[state.size() - 1] = one(x);

	  } 

	REP(i, 0, n)

	{

		char s[15];

		scanf("%s", s);

		REP(j, 0, m)

			if(s[j] == 'H')

				map[i] |= (1 << j);

	}

	REP(i, 0, state.size())

		if(!(state[i] & map[0]))

			dp[0][i][0] = num[i];

	REP(i, 0, state.size())

	{

		if((state[i] & map[0])) continue;

		REP(j, 0, state.size())

		{

			if((state[j] & map[1])) continue;

			if((state[j] & state[i])) continue;

			dp[1][j][i] = max(dp[1][j][i], dp[0][i][0] + num[j]);

		}

	}

	REP(r, 2, n)

		REP(k, 0, state.size())

		{

			if((state[k] & map[r-2])) continue;

			REP(j, 0, state.size())

			{

				if((state[j] & map[r-1]) || (state[j] & state[k])) continue;

				REP(i, 0, state.size())

				{

					if((state[i] & map[r]) || (state[j] & state[i]) || (state[i] & state[k])) continue;

					dp[r][i][j] = max(dp[r][i][j], dp[r-1][j][k] + num[i]);

				}

			}

		}

	int ans = 0;

	REP(r, 0, n)

		REP(i, 0, state.size())

			REP(j, 0, state.size())

				ans = max(ans, dp[r][i][j]);

	printf("%d\n", ans);

	return 0;

}

巴特西

POJ 1185 炮兵阵地（状压dp）（棋盘dp）

最新文章

热门文章

巴特西

POJ 1185 炮兵阵地 （状压dp）（棋盘dp）

最新文章

热门文章

POJ 1185 炮兵阵地（状压dp）（棋盘dp）