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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

BZOJ2755 & SCOI2012 喵星人的入侵  

2013-03-08 11:44:36|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
总算过了,纠结了一个晚上和一个上午,而且是把ZOJ3213的代码直接复制过来并且凭借着BZOJ上时间的平摊以及开O2将总时间折半才AC的。。。
不过我也懒得将map去掉了(由于偷懒所以dp的状态是用map来存的,虽然将其改成数组难度不大,但实在不想麻烦了)
基本就是各种调试和某些莫名奇妙的问题使得程序各种WA,TLE,MLE,RE
最终对了也是莫名奇妙的,虽然正如txh所说的,从一开始就觉得我的代码是完美无缺的,但现实很残酷。。。
基本上蘑菇题的做法就是老老实实坐下来静静地写
不过网上似乎没有题解,当初做的时候碰到几个纠结的问题到网上去搜也没搜到,
所以详细地写一写吧。

题意:
n*m的格子 (max(n,m)<=20 ,min(n,m)<=6)。有三种格子,炮台,障碍,和空地。炮台可以对其周围八个方向的格子造成伤害。现在喵星人从点S出发前往点T,只能走空地,对于任意一种行进路线,其代价为经过的每个格子相邻的炮台个数的和。现在要求你在这个地图上安放一些障碍和炮台(炮台数量要求小于等于K<=15),使得喵星人受到的伤害最大。喵星人会走一条伤害最小的路径。
题解:
明确一点,你一定会使得最终只剩下唯一路径,因为对于不再路径上的点,你都可以用障碍堵住。
所以可以很容易想到简单路径问题,这个问题是经典的插头dp。。。名曰简单但丝毫没看出哪儿简单了,至少我是这么认为的。
参见ZOJ3213,就是求权值和最大的一条简单路径。
本题也就是求一条权值和最大的路径。但是此时有几个问题:
第一,点的代价是不确定的。
第二,一条路径不一定满足题意,因为本题中不容许出现两个点都是空地而在路径中不相邻
第三,起始点是确定的。
所以必须拓展状态。
于是我们新增加一维,记录轮廓线上每个格子的情况,用三进制表示其为空格,炮台还是障碍。
点的代价可算:若该点为炮台,那么代价就是轮廓线上方相邻的空地数目,若该点为空地,那么代价就是轮廓线上方相邻的炮台个数。问题一解决。
由于有了这一维,发现第二个问题也很简单:对于任意一个格子,若其上方或左边是空地却没有插头,那么状态不能转移。问题二解决。
而对于问题三,我们需要在插头转移中注意几点:独立插头只能在S或T新建,插头只能在S或T封住成为独立插头。在S和T,插头不能延续,而且不能新建新的回路。这样最终的答案中只会有两个独立插头。而且必有两个独立插头。
解决了以上问题就只剩下简单的简单路径的插头dp了。。。

  评论这张
 
阅读(585)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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