poj1185--炮兵阵地（状压dp）

本文主要是介绍poj1185--炮兵阵地（状压dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

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

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

Input

Output

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

状压dp，每一行有2^m种状态，然后排除不符合的，相邻两个之间距离要大于等于2，用j & j << 1   j & j << 2 来判断，每一行的状态由上两行决定，所以dp中就要包含两行的状态，才能由一个dp推到另一个dp，dp[i][j][k]表示在第i行的时候，状态为j，i-1行状态为k的最优解。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
int Map[120][12] , state[120][100] , num[120] ;
char str[120][12] ;
int dp[120][100][100] ;
int sum(int x,int m)
{int temp = 0 , i ;for(i = 0 ; i < m ; i++)if( (1<<i) & x )temp++ ;return temp ;
}
int main()
{int n , m , i , j , k , l ;scanf("%d %d", &n, &m) ;memset(dp,0,sizeof(dp)) ;memset(num,0,sizeof(num)) ;for(i = 1 ; i <= n ; i++)scanf("%s", str[i]) ;for(i = 1 ; i <= n ; i++)for(j = 0 ; j < m ; j++){if( str[i][j] == 'P' )Map[i][j] = 1 ;elseMap[i][j] = 0 ;}num[0] = 1 ;state[0][0] = 0 ;int x = 1 << m ;for(i = 1 ; i <= n ; i++){for(j = 0 ; j < x ; j++){if( !(j&(j<<1)) && !(j&(j<<2)) ){for(k = 0 ; k < m ; k++){if( !Map[i][k] && (j&1<<k) > 0 )break ;}if( k == m )state[i][ num[i]++ ] = j ;}}}for(i = 0 ; i < num[1] ; i++){dp[1][i][0] = sum(state[1][i],m);}for(i = 2 ; i <= n ; i++)for(j = 0 ; j < num[i] ; j++)for(k = 0 ; k < num[i-1] ; k++){if( state[i-1][k]&state[i][j] )continue ;for(l = 0 ; l < num[i-2] ; l++){if( state[i-2][l]&state[i][j] )continue ;dp[i][j][k] = max( dp[i][j][k],dp[i-1][k][l] ) ;}dp[i][j][k] += sum(state[i][j],m) ;}int ans = 0 ;for(i = 0 ; i <= num[n] ; i++)for(j = 0 ; j < num[n-1] ; j++)ans = max( ans,dp[n][i][j] ) ;printf("%d\n", ans) ;return 0;
}

这篇关于poj1185--炮兵阵地（状压dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！