poj1185炮兵阵地

炮兵阵地

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 16155		Accepted: 6142

Description

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

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

Input

第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。

Output

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

Source

这道题比较经典，是状态压缩的动态规划。。

Noi 01

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int n,m,ii;
char map[102][11];
int dp[102][61][61];
int line[103];
struct state
{
	int soldler;  //在这种状态下的士兵数
	int sta;	  //将这种二进制状态用十进制表示出来
}state[62];
int Max(int a,int b)
{
	return a>b?a:b;
}

void Init(int mm,int num,int n,int a[])   //递归计算一共有多少种状态。。
{
	if(mm == m+2)
	{
		state[ii].soldler = num;
		state[ii++].sta = n;
		return;
	}
	if(!a[mm-2] && !a[mm-1] && !a[mm] && !a[mm+1] && !a[mm+2])
	{
		a[mm] = 1;
		Init(mm+1,num+1,n+(int)pow(2.0,mm-2),a);
		a[mm] = 0;
		Init(mm+1,num,n,a);
	}
	else
		Init(mm+1,num,n,a);
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(map,0,sizeof(map));
		memset(state,0,sizeof(state));
		ii = 0;
		int a[15] = {0};
		Init(2,0,0,a);
		memset(line,0,sizeof(line));
		for(int i=1;i<=n;i++)
		{
			scanf("%s",map[i]+1);

			for(int j=1;j<=m;j++)
				if(map[i][j] == 'H')
					line[i]+=(int)pow(2.0,j-1);
		}
		int s,t,r,max=0;
		for(s=0;s<ii;s++)
		{
			if( !(state[s].sta&line[1]) )
			{
		dp[1][s][ii-1] = state[s].soldler;
		max = Max(max,dp[1][s][ii-1]);
			}
		}

			for(s=2;s<=n;s++)   //动态规划dp[s][t][r] = num[t] + max{dp[s-1][r][q]}...
				for(t=0;t<ii;t++)
					for(r=0;r<ii;r++)
					{
						if( !(state[t].sta & state[r].sta) && !(state[t].sta&line[s]) )
							for(int q=0;q<ii;q++)
								if( !(state[t].sta & state[q].sta) && !(state[r].sta & state[q].sta) )
								{
									dp[s][t][r] = Max(dp[s][t][r],state[t].soldler+dp[s-1][r][q]);
								}
								max = Max(max,dp[s][t][r]);
					}
		
					printf("%d\n",max);

	}
	return 0;

}