注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

炮兵布阵  

2016-08-06 08:53:49|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 
炮兵布阵 - 杨鸿飞 - 杨鸿飞的博客
如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 
现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵部队之间不能互相攻击,即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内),在整个地图区域内最多能够摆放多少我军的炮兵部队。 
N <= 100;M <= 10。
http://acm.hust.edu.cn/vjudge/contest/126320#problem/C
===================================
        这题跟那个种玉米很像,也只是升级版。
        升级一:因为当前行能否放炮跟前两行有关,所以要记录两行的状态。(时间会多一维)
        升级二:因为要记录两行的状态,空间也会多一维。
        升级三:因为要记录两行的状态,写起来可能会乱(yhf坑了很多道)。
        升级四:求的是最大值,其实也差不多。
====================================
        其实不用担心那么多,这里用了一个跟种玉那题米差不多的优化技巧,因为当前行要相邻两格,就可以预先处理这个。结果发现,原本可能有1024种可能的最后只有60种233。这时zt[i]表示第i种状态,用这个i来做下标,就可以缩短空间,而不是代表状态zt[i]。
====================================

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int MLn=100;
const int MLm=10;
const int MLzt=70;

int zt[MLzt],tp;

int f[MLn+10][MLzt][MLzt],g[MLn+10],s[MLzt];

int n,m;

int S(int x)
{
int sum=0;
for ( ; x>0; x-=(x & -x)) sum++;
return sum;
}

int main()
{
//freopen("cannon.in", "r", stdin);
//freopen("cannon.out", "w", stdout);

cin>>n>>m;

for (int i=1; i<=n; i++)
{
for (int j=0; j<m; j++)
{
char ch; cin>>ch;
g[i]<<=1;
if (ch=='H') g[i]|=1;
}
}

int maxl=(1<<m);

for (int i=0; i<maxl; i++)
if ((i&(i<<1))==0 && (i&(i<<2))==0)
zt[tp]=i,s[tp++]=S(i);

for (int i=0; i<tp; i++)
for (int j=0; j<tp; j++)
{
int zi=zt[i],zj=zt[j];

if ((zi&g[1])+(zj&g[2])>0) continue;

if ((zi&zj)==0) f[1][i][j]=s[i]+s[j];
}

for (int i=1; i<=n-2; i++)
{
for (int j1=0; j1<tp; j1++)
for (int j2=0; j2<tp; j2++)
{
int z1=zt[j1],z2=zt[j2];
if (f[i][j1][j2]>0)
{
for (int k=0; k<tp; k++)
{
int zk=zt[k],&nans=f[i+1][j2][k];
if ((zk&g[i+2])+(zk&z1)+(zk&z2)<1)
nans=max(nans,s[k]+f[i][j1][j2]);
}
}
}
}

int ans=0;

for (int j1=0; j1<tp; j1++)
for (int j2=0; j2<tp; j2++)
ans=max(f[n-1][j1][j2],ans);

cout<<ans;

return 0;
}


  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018