实验讲评2实验讲评2章节.pptVIP

在一条水平路边，有n（2=n=25）个钓鱼湖，从左到右编号为1、2、3、……、n。佳佳有H（ 1=H=16）个小时的空余时间，他希望用这些时间钓到尽量多的鱼。他从湖1出发，向右走，有选择的在一些湖边停留一定的时间钓鱼，最后在某一个湖边结束钓鱼。佳佳测出从第i个湖到第i＋1个湖需要走5*Ti分钟的路，还测出在第i个湖边停留，第一个5分钟可以钓到鱼Fi，以后再每钓5分钟鱼，鱼量减少Di。 为了简化问题，佳佳假设没有其他人钓鱼，也不会有其他因素影响到他钓到期望数量的鱼。请编程求能钓最多鱼的方案。 有n个湖，它们中间依次有一段路程，消耗t[i]单位时间 每个湖i初始单位时间（5分钟）可钓到鱼的数量为f[i] 然后每个单位时间鱼量减少d[i] 问题： 如何设计路线和停留时间，使得钓到的鱼数量最多？ 方法提示： 以每一个湖 I 做为终止点，分别采用贪心法。 1.可用时间= 总时间–路程时间 2.每个单位时间挑选前i个湖中鱼量最大的（排序） 3.反复2，直到可用时间用尽 挑出n个结果中最大的做为最后结果 注意细节： 可能有的湖中鱼的递减量为0 可能有多个结果，根据题意取舍 枚举＋贪心 教学进度 计算机科学与工程系 教学进度 计算机科学与工程系 Google Book You, the best hacker in the world, want to download the books published on Google Book. After some investigation, you found that the address of each page consists of two parts. The first part is the page number, the second part is the signature which is unique for each page. Google Book To get the signature, you can send the query to the server. The query has one parameter, which indicates the page number. The server will return the signature of the required page, and it may also return the signature of some adjacent pages. minimize the number of queries Google Book Sample Input 2 3 1 1 2 2 3 3 3 1 1 1 3 3 3 Sample Output 3 1 区间覆盖问题 贪心策略:选取的区间能覆盖尽可能长的区域,并且保证所有的1-n的范围都给覆盖到 第1步:1开始的区间,取覆盖范围最长的,设为[1,max] 接下来,每次取能覆盖到max+1的最长覆盖区间[s,e], s=max+1 对每个区间，以其起始坐标为关键字，从小到大排序；如果起始坐标相等，则按结束坐标从大到小排序 另一区间覆盖问题 用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超过N(1=N=50)。 例如：M=5个整数1、3、4、8和11表示区间，要求所用线段不超过N=3条 0 1 2 3 4 5 6 7 8 9 10 11 算法分析 如果N=M，那么显然用M条长度为1的线段可以覆盖住所有的区间，所求的线段总长为M。 如果N=1，那么显然所需线段总长为：… 如果N=2，相当于N=1的情况下从某处断开（从哪儿断开呢？） 如果N=k呢？ 钓鱼问题 教学进度 计算机科学与工程系 教学进度 计算机科学与工程系