免费馅饼•SERKOI最新推出了一种叫做“免费馅饼”的游戏。•游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。•游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。•馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。•写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。免费馅饼•输入数据：输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度W（1~99之间的奇数）和高度H（1~100之间的整数）。•接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。•输出数据：输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。分析•我们将问题中的馅饼信息用一个表格存储。表格的第I行第J列表示的是游戏者在第I秒到达第J列所能取得的分值。那么问题便变成了一个类似数字三角形的问题：从表格的第一行开始往下走，每次只能向左或右移动一格或两格，或不移动走到下一行。怎样走才能得到最大的分值。•因此，我们很容易想到用动态规划求解。•F[I,J]表示游戏进行到第I秒，这时游戏者站在第J列时所能得到的最大分值。那么动态转移方程为：F[I,J]=Max{F[I-1,K]}+馅饼的分值(J-2<=K<=J+2)分析•由于动态规划要满足无后效性和最优化原理，所以我们来分析此题是否满足以上两点。首先确定状态，商品不超过5种，而每种采购的数量又不超过5，那么用一个五元组来表示第i种商品买Ai的最小费用。•F（A1，A2，A3，A4，A5）（1）•考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。于是如果我们能够使用第i条商品组合的话，状态就b变为了：•F（A1-SI1，A2-SI2，A3-SI3，A4-SI4，A5-SI5）（2）•这样的话，状态1的费用为状态2的费用加上Si的费用，而状态2的费用必须最低（很显然，用反证法即可），同时，我们也不管状态2是如何来的（因为每一个优惠商品组合的使用是没有限制的），所以本题既满足无后效性，又符合最优化原理，同时还有大量重叠子问题产生，动态规划解决此题是最好不过了。Robots•在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。•问：最多能拾多少垃圾。在最多的情况下，有多少种方案？请举出一种方案来。•数据范围:n<=100,m<=100举例•最多能拾5块。有4种方法。分析：•因为只能向右或者向下走。也就是说不能走回头路。于是考虑动态规划。•设F[i,j]表示从(1,1)点开始走到(i,j)的时候，最多捡了多少垃圾。G[i,j]表示在f[i,j]最大的时候，有多少种方案。C[i,j]=1表示(i,j)点有垃圾。C[i,j]=0表示没有。状态转移方程•根据(i,j)只能从(i-1,j)或者(i,j-1)走过来。•于是f[i,j]=Max{f[i-1,j],f[i,j-1]}+c[i,j].•g[i,j]=g[i-1,j]*k+g[i,j-1]*L。•如果f[i-1,j]+c[i,j]=f[i,j]，则K=1否则K=0。•如果f[i,j-1]+c[i,j]=f[i,j]，则L=1否则L=0。总结•于是我们得到第1，2问的答案。对于第3问，我们只要简单得在动态规划的时候记录一个决策即从哪个方向走过来的就可以了。•时间复杂度O(nm)。附加问题1•怎样使得最少的机器人捡完所有的垃圾？•在这个图中，我们只需要2个机器人就能捡完所有的垃圾。考虑这些机器人组成的路径•假设1号机器人组成的路径是A11,A12,A13..•2号机器人的路径是A21,A22,A23•……………….(Aij代表一个垃圾的位置)•假设看成A12和A11配对，A13和A12配对，A22和A21配对，A23和A22配对的话…•那么N个点一组配对就对应了一组机器人和他们的路径...
