《简单算法.ppt

看一个例子：钓鱼 在一条水平路边，有n(2=n=25)个湖，从左到右序号为1,2,3…n。佳佳有H个小时的空余时间，他希望用这些时间钓鱼。他从1号湖出发向右走，有选择地在一些湖边停留一定的时间来钓鱼，最后在某个湖边结束钓鱼。他已测出，从第i个湖到第i+1个湖要走5*Ti分钟的路。他还测出，在第i个湖的第一个5分钟可钓鱼Fi条，以后每5分钟鱼量减少Di。假定没有其他人钓鱼，也不受其他因素影响，编程求出佳佳钓鱼最多的方案。 题意描述： 佳佳在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，input中均会给出。并且佳佳从任意一个湖走到它下一个湖的时间input中也都给出。 问题： 求一种方案，使得john在有限的h小时中可以钓到尽可能多的鱼。 output中需包括john在所有湖边所呆的时间，以及最后总的钓鱼数。 * * ACM/ICPC程序设计 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 模拟算法 枚举算法 贪心算法 ACM/ICPC程序设计 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Peter最近买了一台电视机，这台电视机有100个频道，从0到99编号。电视的配套遥控器有13个按钮：1 2 3 ↑4 5 6 ↓7 8 9-? -? 0当按↑键时，当前频道编号会增加1(如果当前为99频道，则会切换到0频道)。 如果按↓键，当前频道编号会减小1(如果当前为0频道，则会切换到99频道).当要切换到0~9频道时，可以直接在遥控器上按相应的键。当要切换到 10~99频道时，可以先按- -键，然后按2个与频道编号相对应的数字键(即先按与频道编号的十位数字相对应的键，然后按与个位数字相对应的键)。由于遥控器长时间的使用或者某些未 知原因，最终遥控器上的某些键坏了，不起作用了。现在你的任务是用最少的按键次数来将频道从编号X切换到编号Y。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ACM/ICPC程序设计 Problem 1042 - Qinz喝饮料 Qinz这就要乘飞机去参加百度总决赛了！在飞机上的饮料可是免费的，Qinz大牛可不能错过这次好机会。 飞机上共有n个座位，且排成一列，而且这一列上面都已经有乘客了（编号从1到n）,每个乘客都需要一杯茶或者一杯咖啡。漂亮的空姐正准备给每位乘客送饮料。 在座位的前方有一个供应饮料的机器，可以提供茶叶和咖啡两种饮料，空姐每次可以在供应机处使用容量为 7的托盘,也就是可以放7杯饮料,且每次只可以装茶或者咖啡一种饮料。 空姐每次可以做如下动作： 1:从供应机处移动到第一个座位或从座位移动到供应机，需要一秒钟。 2:从座位i移动到座位i+1或者从座位i+1移动到座位i,需要一秒钟。 3:给每位乘客提供饮料，需要四秒钟。 4:空姐在返回供应机处取饮料需要47秒钟。 Qinz想要知道空姐给所有乘客供应饮料最少需要多长时间 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ACM/ICPC程序设计 这次送茶 咖啡后送 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 由上面的过程可以看到： 1.每个乘客都要被满足，所以必须被服务4秒来倒茶或者饮料。一共是4*n 2.如果空姐这次送饮料最远走到了k，那么来回的时间就是2k， 她可以服务任意7个以内需要她所当前所携带饮料的人(服务最远7个人才能保证总时间最短，为什么？) 3.每次取饮料都需要47秒，所以每次取饮料+47秒。 4.先送茶叶和先送咖啡对空姐来说是一样的。 ACM/I