[POJ1185][NOI2001]炮兵阵地 状压DP

时间:2021-12-13 08:15:41

题目链接: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的更多相关文章

  1. 洛谷P2704 &lbrack;NOI2001&rsqb;炮兵阵地 &lbrack;状压DP&rsqb;

    题目传送门 炮兵阵地 题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图 ...

  2. P2704 &lbrack;NOI2001&rsqb;炮兵阵地 &lpar;状压DP&rpar;

    题目: P2704 [NOI2001]炮兵阵地 解析: 和互不侵犯一样 就是多了一格 用\(f[i][j][k]\)表示第i行,上一行状态为\(j\),上上行状态为\(k\)的最多的可以放的炮兵 发现 ...

  3. &lbrack;NOI2001&rsqb;炮兵阵地 状压DP

    题面: 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图.在每一格平原地形上最多 ...

  4. 【POJ1185】炮兵阵地 状压DP

    感觉总是被一些SB错误所困扰... 差不多还是(模板题)注意数组空间的大小,和对于合法状态的判断. f[i][j][k]=max(f[i][k][j],f[i-1][l][k]+num[j]) (f[ ...

  5. POJ1185 炮兵阵地 —— 状压DP

    题目链接:http://poj.org/problem?id=1185 炮兵阵地 Time Limit: 2000MS   Memory Limit: 65536K Total Submissions ...

  6. TZOJ 4912 炮兵阵地&lpar;状压dp&rpar;

    描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队.一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P" ...

  7. poj - 1185 炮兵阵地 状压DP 解题报告

    炮兵阵地 Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 21553   Accepted: 8363 Description ...

  8. luogu 2704 炮兵阵地 状压dp

    状压的基础题吧 第一次看感觉难上天,后来嘛就.. 套路:先根据自身状态筛出可行状态,再根据地图等其他限制条件筛选适合的状态加入答案 f i,j,k 分别代表 行数,本行状态,上行状态,再累加答案即可 ...

  9. POJ 1185 炮兵阵地 状压dp

    题目链接: http://poj.org/problem?id=1185 炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K 问题描述 司令部的将军们打算在N*M ...

随机推荐

  1. js实现简单的图片轮播

    js代码如下 <script type="text/javascript"> var n=1; var map=new Array(); map[0]=new Imag ...

  2. ZOJ Problem Set - 1048 Financial Management

    我承认这是一道水的不能再水的题,今天一下就做到了,还是无耻的帖上来吧 #include <stdio.h> int main() { double sum=0; for(int i=1;i ...

  3. 为什么有禁用Mac系统的Spotlight的需求:

    一.为什么有禁用Mac系统的Spotlight的需求: 有的网友由于使用的是相对较老的苹果电脑在运行较新的系统:也有可能你是个速度控,受不了偶尔卡卡顿顿的操作,必须将所有导致卡顿的原因全部消除:也有可 ...

  4. Mac下 Octave 中plot 无法绘制

    在coursera看机器学习课程的时候用到Octave来做数据处理,但是装了之后用plot画图时就会报错: set terminal aqua enhanced title "Figure ...

  5. Zookeeper-Zookeeper的配置

    前面两篇文章介绍了Zookeeper是什么和可以干什么,那么接下来我们就实际的接触一下Zookeeper这个东西,看看具体如何使用,有个大体的感受,后面再描述某些地方的时候也能在大脑中有具体的印象.本 ...

  6. HDU 5821 Ball &lpar;贪心排序&rpar; -2016杭电多校联合第8场

    题目:传送门. 题意:T组数据,每组给定一个n一个m,在给定两个长度为n的数组a和b,再给定m次操作,每次给定l和r,每次可以把[l,r]的数进行任意调换位置,问能否在转换后使得a数组变成b数组. 题 ...

  7. Ext JS学习第五天 Ext&lowbar;window组件(一)

    此文来记录学习笔记 •第一个组件:Ext.window.Window.对于组件,也就是Ext最吸引开发者的地方,那么我们要真正的使用Ext的组件,首先必须学会阅读API文档. –xtype:组件的别名 ...

  8. Eclipse—怎样为Eclipse开发工具中创建的JavaWebproject创建Servlet

    在博客<在Eclipse中怎样创建JavaWebproject>中图文并茂的说明了Eclipse中创建JavaWebproject的方法,本篇博客将告诉大家怎样为Eclipse开发工具中创 ...

  9. poj&lowbar;2115C Looooops&lpar;模线性方程&rpar;

    题目链接:http://poj.org/problem?id=2115 C Looooops Time Limit: 1000MS   Memory Limit: 65536K Total Submi ...

  10. 芝麻HTTP:TensorFlow基础入门

    本篇内容基于 Python3 TensorFlow 1.4 版本. 本节内容 本节通过最简单的示例 -- 平面拟合来说明 TensorFlow 的基本用法. 构造数据 TensorFlow 的引入方式 ...