题目链接:http://poj.org/problem?id=1185
很裸的状压,考虑对于一行用二进制储存每一种的状态,但是状态太多了做不了。
观察到有很多状态都是不合法的,于是我们预处理出合法的状态,发现只有60种,然后随便DP一下就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M;
char G[][];
int s[],cnt[],scnt=,ban[];
int f[][][];
int main(){
memset(ban,,sizeof(ban));
memset(f,,sizeof(f));
memset(cnt,,sizeof(cnt));
memset(s,,sizeof(s));
scanf("%d%d",&N,&M);
for(int i=;i<=N;i++) scanf("%s",G[i]);
for(int i=;i<=N;i++)
for(int j=;j<M;j++)
if(G[i][j]=='H')
ban[i]|=(<<j);
int tmp=<<M;
for(int i=;i<tmp;i++){
bool flag=true;
for(int j=;j<M;j++){
int tmp=((i&(<<j))>)+((i&(<<j+))>)+((i&(<<j+))>);
if(tmp>){
flag=false;
break;
}
}
if(flag){
s[++scnt]=i;
for(int j=;j<M;j++)
if(i&(<<j))
cnt[scnt]++;
}
}
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
f[][][i]=cnt[i];
for(int i=;i<=scnt;i++)
if((s[i]&ban[])==)
for(int j=;j<=scnt;j++)
if((s[i]&s[j])==&&(s[j]&ban[])==)
f[][j][i]=max(f[][j][i],f[][][j]+cnt[i]);
for(int i=;i<=N;i++)
for(int j=;j<=scnt;j++)
if((s[j]&ban[i-])==)
for(int k=;k<=scnt;k++)
if((s[j]&s[k])==&&(s[k]&ban[i-])==)
for(int t=;t<=scnt;t++)
if((s[j]&s[t])==&&(s[k]&s[t])==&&(s[t]&ban[i])==)
f[i][k][t]=max(f[i][k][t],f[i-][j][k]+cnt[t]);
int Ans=;
for(int i=;i<=scnt;i++)
for(int j=;j<=scnt;j++)
Ans=max(Ans,f[N][i][j]);
printf("%d\n",Ans);
return ;
}
[POJ1185][NOI2001]炮兵阵地 状压DP的更多相关文章
-
洛谷P2704 [NOI2001]炮兵阵地 [状压DP]
题目传送门 炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图 ...
-
P2704 [NOI2001]炮兵阵地 (状压DP)
题目: P2704 [NOI2001]炮兵阵地 解析: 和互不侵犯一样 就是多了一格 用\(f[i][j][k]\)表示第i行,上一行状态为\(j\),上上行状态为\(k\)的最多的可以放的炮兵 发现 ...
-
[NOI2001]炮兵阵地 状压DP
题面: 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图.在每一格平原地形上最多 ...
-
【POJ1185】炮兵阵地 状压DP
感觉总是被一些SB错误所困扰... 差不多还是(模板题)注意数组空间的大小,和对于合法状态的判断. f[i][j][k]=max(f[i][k][j],f[i-1][l][k]+num[j]) (f[ ...
-
POJ1185 炮兵阵地 —— 状压DP
题目链接:http://poj.org/problem?id=1185 炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions ...
-
TZOJ 4912 炮兵阵地(状压dp)
描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P" ...
-
poj - 1185 炮兵阵地 状压DP 解题报告
炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 21553 Accepted: 8363 Description ...
-
luogu 2704 炮兵阵地 状压dp
状压的基础题吧 第一次看感觉难上天,后来嘛就.. 套路:先根据自身状态筛出可行状态,再根据地图等其他限制条件筛选适合的状态加入答案 f i,j,k 分别代表 行数,本行状态,上行状态,再累加答案即可 ...
-
POJ 1185 炮兵阵地 状压dp
题目链接: http://poj.org/problem?id=1185 炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K 问题描述 司令部的将军们打算在N*M ...
随机推荐
-
js实现简单的图片轮播
js代码如下 <script type="text/javascript"> var n=1; var map=new Array(); map[0]=new Imag ...
-
ZOJ Problem Set - 1048 Financial Management
我承认这是一道水的不能再水的题,今天一下就做到了,还是无耻的帖上来吧 #include <stdio.h> int main() { double sum=0; for(int i=1;i ...
-
为什么有禁用Mac系统的Spotlight的需求:
一.为什么有禁用Mac系统的Spotlight的需求: 有的网友由于使用的是相对较老的苹果电脑在运行较新的系统:也有可能你是个速度控,受不了偶尔卡卡顿顿的操作,必须将所有导致卡顿的原因全部消除:也有可 ...
-
Mac下 Octave 中plot 无法绘制
在coursera看机器学习课程的时候用到Octave来做数据处理,但是装了之后用plot画图时就会报错: set terminal aqua enhanced title "Figure ...
-
Zookeeper-Zookeeper的配置
前面两篇文章介绍了Zookeeper是什么和可以干什么,那么接下来我们就实际的接触一下Zookeeper这个东西,看看具体如何使用,有个大体的感受,后面再描述某些地方的时候也能在大脑中有具体的印象.本 ...
-
HDU 5821 Ball (贪心排序) -2016杭电多校联合第8场
题目:传送门. 题意:T组数据,每组给定一个n一个m,在给定两个长度为n的数组a和b,再给定m次操作,每次给定l和r,每次可以把[l,r]的数进行任意调换位置,问能否在转换后使得a数组变成b数组. 题 ...
-
Ext JS学习第五天 Ext_window组件(一)
此文来记录学习笔记 •第一个组件:Ext.window.Window.对于组件,也就是Ext最吸引开发者的地方,那么我们要真正的使用Ext的组件,首先必须学会阅读API文档. –xtype:组件的别名 ...
-
Eclipse—怎样为Eclipse开发工具中创建的JavaWebproject创建Servlet
在博客<在Eclipse中怎样创建JavaWebproject>中图文并茂的说明了Eclipse中创建JavaWebproject的方法,本篇博客将告诉大家怎样为Eclipse开发工具中创 ...
-
poj_2115C Looooops(模线性方程)
题目链接:http://poj.org/problem?id=2115 C Looooops Time Limit: 1000MS Memory Limit: 65536K Total Submi ...
-
芝麻HTTP:TensorFlow基础入门
本篇内容基于 Python3 TensorFlow 1.4 版本. 本节内容 本节通过最简单的示例 -- 平面拟合来说明 TensorFlow 的基本用法. 构造数据 TensorFlow 的引入方式 ...