题目名称	301. [NOI 2001]炮兵阵地
输入输出	`cannon.in/out`
难度等级	★★☆
时间限制	5000 ms (5 s)
内存限制	256 MiB
测试数据	10
题目来源	BYVoid 于2009-03-20加入
开放分组	全部用户
提交状态
分类标签	NOI 动态规划状态压缩位运算
	分享题解

通过：209，提交：549，通过率：38.07%
Gilgamesh	100	0.039 s	3.23 MiB	C++
AAAAAAAAAA	100	0.046 s	2.12 MiB	C++
Gilgamesh	100	0.051 s	3.77 MiB	C++
Shirry	100	0.065 s	2.12 MiB	C++
RP++	100	0.071 s	1.80 MiB	C++
kxxy	100	0.075 s	2.70 MiB	C++
LGLJ	100	0.079 s	4.20 MiB	C++
超人	100	0.089 s	7.02 MiB	C++
Fancy、	100	0.099 s	5.39 MiB	C++
Houjyou	100	0.102 s	4.17 MiB	C++

本题关联比赛
专项训练十题
状态压缩DP
状态压缩DP练习

关于炮兵阵地的近10条评论(全部评论)
要么每一行的状态预处理忘看0了要么我每一行枚举状态忘了s[0]存的是状态个数了，反正我俩都改过就是忘了俩一块改，我真棒！在大街上倒立游泳 2023-07-28 16:29 16楼
回复 @ : 我回复我自己 cb 2021-07-02 16:46 15楼
位运算注意加括号（严格优先级太低） fsdh 2020-10-08 22:03 14楼
数组开大了，给我报错RE。。。。 Hale 2019-05-29 12:56 13楼
评测姬抽了嘛 Shirry 2017-03-25 11:04 12楼
事实证明popcount的优势并不明显 Rapiz 2017-03-02 20:04 11楼
md数组开小没1a…… confoo 2017-03-02 19:57 10楼
LOSER 2016-10-22 17:36 9楼
poj上过不去QAQ 牧殇 2016-10-07 14:43 8楼
dp算法，之前两行遗传，记录遗传信息并二进制编码，加上&\|!运算 FoolMike 2016-02-23 10:24 7楼

301. [NOI 2001]炮兵阵地

★★☆ 输入文件：cannon.in 输出文件：cannon.out 简单对比
时间限制：5 s 内存限制：256 MiB

【题面描述】

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

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

Image:Cannon.gif

【输入格式】

文件的第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

【输出格式】

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

【输入样例】

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

【输出样例】