今天好高兴啊~在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：这个星期肯定是点名黄金周！这星期到现在为止，没一个老师不点名的 >_< ，幸好我的预感准确。好，我乖乖地去上课就是~