状态压缩DP-炮兵阵地（POJ 1185）

Description

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 

Input

Output

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

Source

【题目大意】类似于上面一道题，一个方格组成的矩阵，每个方格可以放大炮用0表示，不可以放大炮用1表示（原题用字母），让放最多的大炮，大炮与大炮间不会互相攻击。

【分析】这道题与上一题的不同之处在于，他需要保存上一层的状态以为对应的上上层的状态，因此需要一个三维的数组来保存数据的dp[][][],第一维表示层数，第二维表示当前层的状态的下标，第三维，表示上一层的状态的下标；下标与状态值得对应关系存放在数组goodForPut[]中；

【状态表示】dp[i][j][k] 表示第j行状态为j，且上一层状态为k的情况下最大炮兵个数。 

【状态转移方程】dp[i][j][k] =max(dp[i][j][k],dp[i-1][m][j] +num[goodForPut[m]]); num[i]为i状态中1的个数 

java代码

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

import org.omg.CosNaming.IstringHelper;

public class Main {
	
	// 存放的是大炮的总数
	// 三维数组，第一维表示层数，第二维表示当前层的状态的下标，第三维，表示上一层的状态的下标；
	//下标与状态值得对应关系存放在goodForPut中；
	private int dp[][][];
	
	private int isOk[];
	private int goodForPut[];
	private int goodCount;
	private int allStatusCount;

	public Main(int M, int N) {
		
		allStatusCount = 1 << N;
		// 需要保存两层状态
		
		// 值为当前最大的大炮的数量

		goodForPut = new int[(1 << N)];
		isOk = new int[M];

		Arrays.fill(goodForPut, 0);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin = new Scanner(new BufferedInputStream(System.in));
		int M, N;

		M = cin.nextInt();
		N = cin.nextInt();
		Main ma = new Main(M, N);
		String str;
		int bit;

		for (int i = 0; i < M; i++) {
			bit = 0;
			str = cin.next().trim();
			for (int j = 0; j < N; j++) {
				bit = (bit << 1);
				// P 可以放大炮，用1表示，H不能放大炮，用0表示
				if (str.charAt(j) == ‘P‘) {
					bit = bit | 1;
				}
			}
			ma.isOk[i] = bit;
		}

		System.out.println(ma.getMostCount());
	}

	private int getMostCount() {
		// TODO Auto-generated method stub
		prepareIt();
		
		//显然0下标对应的是0状态
		dp[0][0][0] = 0;
		
		int max = 0;
		// 从零层开始，
		for (int i = 1; i < isOk.length+1; i++) {
			for (int j = 0; j < goodCount; j++) {
				for (int m = 0; m < goodCount; m++) {
					
					if (dp[i - 1][j][m] == -1) {
						continue;
					}
					
					for (int k = 0; k < goodCount; k++) {
						// 判断是否是可以放大炮的哈
						if ((goodForPut[k] & isOk[i - 1]) == goodForPut[k]) {
							// 与前两行比较；
							// 与上一层的状态比较，
							if ((goodForPut[k] & goodForPut[j]) == 0) {
								// 上上一层的状态；
								if ((goodForPut[k] & goodForPut[m]) == 0) {
									dp[i][k][j] = Math.max(
											dp[i][k][j],
											dp[i - 1][j][m]
													+ num(goodForPut[k]));
									if(i == isOk.length){
										max = Math.max(max,
												dp[i][k][j]);
									}
								}
							}
						}
					}
				}
			}
		}
		return max;
	}

	private int num(int x) {
		// TODO Auto-generated method stub
		// 获取1的个数
		int cnt = 0;
		while (x != 0) {
			cnt++;
			x &= (x - 1);
		}
		return cnt;
	}

	private void prepareIt() {
		// TODO Auto-generated method stub
		int count = 0;
		int max = 0;
		// 建立下标与状态的对应关系
		for (int i = 0; i < allStatusCount; i++) {
			if ((i & (i << 1)) == 0) {
				if ((i & (i << 2)) == 0) {			
					goodForPut[count] = i;
					max = Math.max(max, i);
					count++;
				}
			}
		}
		
		goodCount = count;
		
		dp = new int[isOk.length + 1][goodCount][goodCount];
		for (int i = 0; i < dp.length; i++) {
			for (int j = 0; j < goodCount; j++) {
				Arrays.fill(dp[i][j], -1);
			}
		}
		
	}

}

状态压缩DP-炮兵阵地（POJ 1185）,布布扣,bubuko.com

状态压缩DP-炮兵阵地（POJ 1185）

原文：http://blog.csdn.net/haizi8888/article/details/23883377