学步园

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<queue>

using namespace std;

/*为大家方便明白，注释比较多。该题可深化动态规划，学会滚动数组，状态压缩等知识。*/

char map[101][11];//地图
int surface[101];//地形状态压缩数
int state[61];//所有的合法状态压缩数
int stanum[61];//相应状态的炮兵数量
int f[101][61][61];//动态规划存储矩阵

void clear()
{

	memset(map,0,sizeof(map));
	memset(surface,0,sizeof(surface));
	memset(state,0,sizeof(state));
	memset(stanum,0,sizeof(stanum));
	memset(f,0,sizeof(f));
}

int main()
{
	int row,col;
	while(cin>>row>>col)
	{
		for (int i=0;i<row;i++)
			cin>>map[i];
		/*因为最大列数不大于10，故可用dp进行状态压缩
		注：所谓状态压缩即如：PHPP 可以用二进制0100表示，用十进制存储为4。
		本题因其反向对称性，为了方便压缩，故上边实例压缩成0010,用2表示，不影响求解。*/
		for (int i=0;i<row;i++)
			for (int j=0;j<col;j++)
			{
				if(map[i][j] == 'H') 
					surface[i] +=1<<j;
			}
			/*同地图状态压缩，对排列阵型的状态进行压缩，并算出相应阵型的数量。
			//如PHPP有0001 0010 1000 1001 摆法，相应的压缩为 1 2 6 7 相关人数为 1 1 1 2*/
			int snum=0;
			for(int i=0;i< (1<<col);i++)
			{
				int temp=i;
				if( (i<<1)&i || (i<<2)&i ) 
					continue;//判断图是否兼容 
				stanum[snum] = temp%2;
				while (  temp = (temp>>1) )
					stanum[snum] += temp%2;//计算能放多少个炮兵 
				state[snum++]=i;
			}
			/*动态规划状态转移方程：
			//f[i][j][k] = max{f[i-1][k][l]+stanum[j]},
			//f[i][j][k]表示第i行状态为s[j],第i-1行状态为s[k]的最大炮兵数
			//枚举l的每种状态,且state[j],state[k],state[l],地形互不冲突*/
			//第一行放置所有炮兵情况
			for (int i=0;i<snum;i++)
			{
				/*该处就表现出状态压缩的强大好处了，下边的语句进行状态和地形的判断
				//仅仅进行一次位与操作，即可知道是否摆放与地形冲突。以后状态判断类似*/
				if(state[i] & surface[0])
					continue;
				f[0][i][0]=stanum[i];
			}
			//第二行放置所有炮兵情况
			for (int i=0;i<snum;i++)
			{
				if(state[i] & surface[1]) continue;
				for (int k=0;k<snum;k++)
				{
					if(state[k] & surface[0]) continue;
					if(state[i] & state[k]) continue;
					f[1][i][k] = f[1][i][k] > (f[0][k][0]+stanum[i]) ? f[1][i][k] : (f[0][k][0]+stanum[i]) ;
				}
			}
			//之后的炮兵放置情况。如果还是不明白，请仔细揣摩上边给出的动态规划状态转移方程
			for (int i=2;i<row;i++)
				for (int j=0;j<snum;j++)
				{
					if(surface[i] & state[j]) continue;
					for(int k=0;k<snum;k++)
					{
						if(surface[i-1] & state[k]) continue;
						if(state[j] & state[k]) continue;
						for (int l=0;l<snum;l++)
						{
							if(state[l] & surface[i-2]) continue;
							if(state[j] & state[l] || state[k] & state[l]) continue;
							f[i][j][k] = f[i][j][k] > (f[i-1][k][l]+stanum[j]) ?
								f[i][j][k] : (f[i-1][k][l]+stanum[j]) ;
						}
					}
				}
				//找出最优解
				if(row ==0 ) cout<<"0"<<endl;
				else
				{
					int max=0;
					for (int i=0;i<snum;i++)
						for (int j=0;j<snum;j++)
						{
							if(max<f[row-1][i][j]) max=f[row-1][i][j];
						}
						cout<<max<<endl;
				}
	}
	system("pause");
	return 0;
}