先看同一行哪一些方案可以放置，以减小时间复杂度（老套路）查看的方法是看左边第一、二，右边第一、二 不能跟自己这个位置同时有1 然后统计这个方法包含的炮兵数，统计方法是线性dp，通过lowbit（树状数组的东西），转移计数。（每个方案的炮兵数量是这个方案的二进制串去除最低位的1的炮兵数量+1）最后一行
展开全文
本题算是[SCOI2005]互不侵犯KING (nowcoder.com)这道题的升级版，在互不侵犯这道题里面除了同一行的限制，上下行的限制仅仅包含一行。而在这道题里面则是包含了两行。
那么我们可以像互不侵犯那样将状态转移数组设成dp[i][j]，i表示某一层，j表示当前层的二进制数吗？当然不
展开全文
思路 ,这么小的数据范围当然要想到状态压缩.我们把放置炮兵的位置变成,不放炮兵为.这题比较猥琐的一点就是会影响到能否放炮兵的有前两行.这样至少需要三维,记录当前到哪行以及前两行的状态.这样不能承受.由于这特殊的"十字",每行两个炮兵之间至少要两个格子.打个表可以发现满足条件的状态大概只有六十几个,这
展开全文
题目描述司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑***域所示：
展开全文
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std
展开全文
思路：
题目要求求出最多的炮兵数，对于一个位置可以选择放也可以不放，而之后可以根据这次的选择更新下一步的选择。考虑状态压缩dp。一行一行的放炮兵，因为题目中给出的炮兵攻击范围是一个十字，所以在判断这个炮兵能不能放的时候需要知道上一行炮兵和上上行放在哪了，也要知道此时放的炮兵所在的这一行里左边的放炮兵
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
