ACMICPC程序设计.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程序设计 艾庆兴 模拟算法 枚举算法 贪心算法 ACM/ICPC程序设计 ACM/ICPC程序设计 Problem 1042 - Qinz喝饮料 Qinz这就要乘飞机去参加百度总决赛了！在飞机上的饮料可是免费的，Qinz大牛可不能错过这次好机会。 飞机上共有n个座位，且排成一列，而且这一列上面都已经有乘客了（编号从1到n）,每个乘客都需要一杯茶或者一杯咖啡。漂亮的空姐正准备给每位乘客送饮料。 在座位的前方有一个供应饮料的机器，可以提供茶叶和咖啡两种饮料，空姐每次可以在供应机处使用容量为 7的托盘,也就是可以放7杯饮料,且每次只可以装茶或者咖啡一种饮料。 空姐每次可以做如下动作： 1:从供应机处移动到第一个座位或从座位移动到供应机，需要一秒钟。 2:从座位i移动到座位i+1或者从座位i+1移动到座位i,需要一秒钟。 3:给每位乘客提供饮料，需要四秒钟。 4:空姐在返回供应机处取饮料需要47秒钟。 Qinz想要知道空姐给所有乘客供应饮料最少需要多长时间 ACM/ICPC程序设计 这次送茶 咖啡后送 由上面的过程可以看到： 1.每个乘客都要被满足，所以必须被服务4秒来倒茶或者饮料。一共是4*n 2.如果空姐这次送饮料最远走到了k，那么来回的时间就是2k， 她可以服务任意7个以内需要她所当前所携带饮料的人(服务最远7个人才能保证总时间最短，为什么？) 3.每次取饮料都需要47秒，所以每次取饮料+47秒。 4.先送茶叶和先送咖啡对空姐来说是一样的。 ACM/ICPC程序设计 由此得到算法：模拟空姐送饮料的过程！！ 0.T=4*n。(提前计算给每个乘客倒水的时间，以后则不用算了) 1.从服务台接7杯茶，送到距离最远的7个还想喝茶的乘客。 T=T+47(服务台接水时间)+2*i(i是当前还需要喝茶的最远的乘客的位置) 2.重复1过程，直到没有想喝茶而且还没有喝到茶的人。 3.把茶叶换咖啡，重复1,2过程。 ACM/ICPC程序设计 模拟算法的本质就是把题意理清，并用编程进行模拟，得出最后的结果。 此类题目往往比较容易理解大意，但有很多细节问题需要处理，而且有些复杂的题目的编程复杂度很高，代码量巨大，所以优秀的代码能力是解决模拟题目的利器 贪心算法 简化背包问题 有n(n=100000)个物品，每个物品的价值是wi(1=i=n)，重ci(1=i=n)现在从中挑总重为k的物品，使得这重量为k的物品价值之和最大，问最大的价值maxw是多少。 PS:物品可以被切割，比如价值为2，重量为2的物品可以被切成两个价值为1，重量为1的物品。 很容易想到：性价比！ 用更少的重量得到更大的价值！ 用w[i]/c[i]得到x[i]表示性价比，并对x[i]排序 从性价比最高的物品开始，如果当前剩余的质量leftk=c[i]，那么就把这个物品全部装进背包；如果leftkc[i]，那么就把这个物品切开，把重量为leftk的一部分装进背包。 装进去的全部物品的价格就是所求的最大值 贪心算法的本质就是根据当前的状态选择当前的最优决策，并一直执行下去直到问题解决。 但不是每一道题目的贪心算法都是正确的，贪心算法的正确性需要得到严谨的证明。 想一想：如果题意变成，n=1000，不能切割物品，给一个容量为k的背包，问：在不超出背包容量的情况下，所装物品的最大价值是多少? 这样还可以用贪心算法么? Extended Lights Out (zju 1354) 有一个5行6列的按钮阵列，每个按钮有一盏灯，当它被按下，它和它相邻四个(上下左右)的灯状态改变一次(亮-灭 或灭-亮) 现在给出了这个阵列的初始亮灭状态，找一种操作让灯全灭。 分析 显然按键是顺序无