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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 577 & SRM 578  

2013-05-22 20:45:56|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
果断一起更。。

==========================SRM 577==============

500pt的题是道神题无误,开始困扰了我好久。
题意:8*8的网格,有些点是黑点,按照一定顺序放上这些点,放上一个点的权值是已经放的点中离其曼哈顿距离最远的点到它距离。求权值和最小的安放顺序。
题解:两个点(x1,y1),(x2,y2)的曼哈顿距离为max(abs((x1+y1)-(x2+y2)),abs((x1-y1)-(x2-y2))。我们将所有点(x,y)替换成点(x+y,x-y)。记p=x+y,q=x-y。
那么放上一个点的权值只和之前的p的最大最小值和q的最大最小值有关。
然后开始dp了,记下那四个最值为状态,表示坐标在这些最值中的点的最小权值安放。
每次选择一个点,扩大范围,然后将落在这个扩大的范围中的点的代价算进去即可。

1000pt的题目是个最小割,其实想想应该想得出来的,但是落下了心理阴影,一旦一道题往最小割上面想的话,如果不是很显然,呢么一定不会继续想下去了。。
感觉我真心傻×到爆了。

========================SRM 578===============
没啥可说的,很少的我全部都会的一场SRM。
当然我是受到了很大的打击的。T_T
以后慢慢说吧。
  评论这张
 
阅读(197)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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