ACM算法-动态规划课件.ppt

《ACM算法-动态规划课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计计算机学院刘春英7/29/20211今天，你了吗？AC7/29/20212每周一星（3）：liuzewei7/29/20213第四讲动态规划(1)（Dynamicprogramming）7/29/20214先热身一下——7/29/20215（1466）计算直线的交点数问题描述：平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。输入：n（n<=20）输出：每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数。样例输入4样例输出034567/29/2021

2、6思考2分钟:如何解决?7/29/20217初步分析:我们将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3与直线1和直线2最多有两个交点…….，直线n和其他n-1条直线最多有n-1个交点，由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+……(n-1)=n(n-1)/2,但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？7/29/20218容易列举出N=1,2,3的情况：00，10，2，3如果已知

3、条与其余直线全部平行=>无交点；2、第四条与其中两条平行，交点数为(n-1)*1+0=3;3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为：（n-2）*2+0=4或者(n-2)*2+1=54、第四条直线不与任何一条直线平行，交点数为：(n-3)*3+0=3或者(n-3)*3+2=5或者(n-3)*3+3=6即n=4时，有0个，3个，4个，5个，6个不同交点数。7/29/20219从上述n=4的分析过程中，我们发现：m

4、条直线的交点方案数=（m-r）条平行线与r条直线交叉的交点数+r条直线本身的交点方案=（m-r）*r+r条之间本身的交点方案数（1<=r<=m）7/29/202110一、数塔问题有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。7/29/202111用暴力的方法，可以吗？7/29/202112试想一下：这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（2^30=1024^3

5、>10^9=10亿）。7/29/202113所以，不可以如此暴力！！！7/29/202114考虑一下：从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。7/29/

6、202115Understand?7/29/202116二、思考题：最长有序子序列I012345678Num[I]147258369请回答：穷举（暴力）方法的时间复杂度是多少？7/29/202117解决方案：I012345678Num[I]147258369F[I]1232343457/29/202118三、HDOJ_1160FatMouse'sSpeed题目链接SampleInput600813006000210050020001000400011003000600020008000140060001

7、20020001900SampleOutput445977/29/202119题目分析：设Mice[i].W表示第i只老鼠的重量，Mice[i].S表示第i只老鼠的速度。我们先对Mice进行排序，以W为第一关键字，从小到大，S为第二关键字，从大到小。设f[i]为Mice[i]至Mice[n]最长的序列长度。考虑某一个f[i]，则有：f[i]=max(f[i],f[j]+1)(1<=jMice[j].W，Mice[i].S

8、1,2,...,n)。7/29/202120Qestion:两个问题有本质区别吗？7/29/202121思考（期末考试题）：SuperJumping!Jumping!Jumping!7/29/202122解题思路？7/29/202123四、HDOJ_1159CommonSubsequence题目链接SampleInputabcfbcabfcabprogrammingcontestabcdmnpSampleOutput4207/29/