11. 贪心及动态规划专题(二).ppt

课程成绩考核评定标准 一、成绩构成 1、平时成绩：30% 2、期末论文：70% 二、平时成绩构成： 1、参与校赛与平时OJ练题：20% 2、平时出勤：10% 三、期末论文类型及要求 论文格式要求 需选择某一专题的深入研究 如：线段树、树状数组，网络流等等，可以自己任意选择，题目范围涉及各个算法方面。 要求：要有该专题的理论描述，自己完成的典型题目，并对题目给出解题分析和实现代码（需加注释），选题要有新意，有一定难度。 四、课件下载邮件及密码 Email：UESTCACM@126.com Password：123666 五、论文交付 电子文档请发送到wxiaoping325@163.com，纸质文档交付时间与地点为：第12、13周星期二晚A402，第14、15、16周星期二晚科研楼A227。若有改变或其它通知，将公布在UESTCACM@126.com。 Help Jimmy 问题描述 问题描述 问题描述 2、解题思路 2、解题思路 2、解题思路 3、参考程序 3、参考程序 3、参考程序 3、参考程序 最长上升子序列 问题描述 2、解题思路 2、解题思路 3、参考程序 3、参考程序 最长公共子序列 问题描述 2、解题思路 解题思路 3、参考程序 3、参考程序 陪审团的人选 问题描述 问题描述 2、解题思路 2、解题思路 2、解题思路 3、参考程序 3、参考程序 3、参考程序 3、参考程序 初始条件，只能确定f(0, 0) = 0。由此出发，一步步自底向上递推，就能求出所有的可行方案f(m, k)( -20×m ≤ k ≤ 20×m)。 实际解题的时候，会用一个二维数组f 来存放f(j, k)的值。而且，由于题目中辩控差的值k 可以为负数，而程序中数租下标不能为负数，所以，在程序中不妨将控辩差的值都加上20×m，以免下标为负数导致出错，即题目描述中，如果控辩差为0，则在程序中控辩差为20×m。 #include stdio.h #include stdlib.h #include memory.h int f[30][1000]; int Path[30][1000]; int P[300]; //控方打分 int D[300]; //辩方打分 int Answer[30]; //存放最终方案的人选 int CompareInt(const void * e1, const void * e2) { return * ((int *) e1) - * ((int *) e2); } int main(void) { int i, j, k; int t1, t2; int n, m; int nMinP_D; //控辩差偏移值 int nCaseNo;//测试数据编号 nCaseNo=0; scanf(%d%d, n, m); while(n+m) { nCaseNo++; for(i=1;i=n;i++) scanf(%d%d, P[i], D[i]); memset(f, -1, sizeof(f)); memset(Path, 0, sizeof(Path)); nMinP_D=m*20; //题目中的控辩差为0 //对应到程序中控辩差就是m*20 f[0][nMinP_D]=0; //选0 个人控辩差为0 的方案，其控辩和就是0 * */35 * 第十一讲 贪心与动态规划专题（二） ACM算法与程序设计 数学科学学院：汪小平 wxiaoping325@163.com 1、问题描述 Help Jimmy 是在下图所示的场景上完成的游戏： 场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。 Jimmy 老鼠在时刻0 从高于所有平台的某处开始下落，它的下落速度始终为1 米/秒。当Jimmy 落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1 米/秒。当Jimmy 跑到平台的边缘时，开始继续下落。Jimmy 每次下落的高度不能超过MAX 米，不然就会摔死，游戏也会结束。 设计一个程序，计算Jimmy 到地面时可能的最早时间。 输入数据 第一行是测试数据的组数t（0 = t = 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N 是平台的数目（不包括地面），X 和Y 是Jimmy 开始下落的位置的横竖坐