Fresh Energy

           Nerver say die!

IT博客 首页 新随笔 联系 聚合 管理
  84 Posts :: 0 Stories :: 197 Comments :: 0 Trackbacks
今天好高兴啊~在pku AC了四题。基本上题题都有收获。

首先是pku1018,一个由若干设备串联而成的通信系统,每个设备可以从不同的制造商处购得,它们的带宽和价格不同。整个系统的总带宽B是各设备的最小带宽,价格P是整个系统的总价格。求B/P的最大值。我想了很久很久,都不会做。郁闷中打开了几个discuss看,突然看见一句很启发的话:枚举B,把B/P两个变量的求解化为只求P的最大值。马上恍然大悟啊,数学中都经常用这种思想的,当需要研究多个变量是,把其中一个先设为常量,观察另外一个变量的变化。于是,问题就迎刃而解了:设max为所有设备最大带宽的最小值,min为所有设备最小带宽的最小值,对w=[min,max]进行枚举,在带宽大于w的前提下,在每个设备中选择最便宜的来买。在这个过程中记录P的最小值。途中求出这若干次枚举中B/P的最大值。

然后是pku1083,Moving Tables,开始想的时候觉得好像很复杂,AC的人数也不够800,本来怕太难,想一下就算的。没想到把房间的编号统一一下之后,居然就变得和王晓东的《算法设计题解》里面的会场安排问题几乎一模一样了。^_^  转化之后,三下五除二就写出来了,好爽啊~

接下来是一道中文的..pku1088,滑雪问题。给定一个R*C的滑雪场,矩阵中的数字是此点的高度,当且仅当高度减小,则可以滑向上下左右相邻的四个点之一。要求找出一条最长的滑雪路径的长度。这题也是一样,转化一下就成了经典的DP题:按高度从小到大排一下序,就成了类似于最长递增子序列的问题啦~不过它的条件是两个格之间相邻,而不是‘值的递增’。
经典问题就是经典问题啊,到处都有它们的用武之地,呵呵。

最后做的是一道图论的水题,可是我下的pku题目分类里面写的却是DP。用晓鸣的图论基本算法中的Floyd加工一下就得出结果了。也算是加深了对模板应用的熟练程度哈。

PS:这个星期肯定是点名黄金周!这星期到现在为止,没一个老师不点名的 >_< ,幸好我的预感准确。好,我乖乖地去上课就是~
posted on 2007-04-04 23:30 zhouditty 阅读(430) 评论(1)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: 续:省赛倒数18天 2007-04-05 01:36 踏雪赤兔
  回复  更多评论
  

只有注册用户登录后才能发表评论。