文档介绍：线型动态规划
第1页，共59页，编辑于2022年，星期一
带权有向的多段图问题
给定一个带权的有向图，要求从点A到点D的最短路径。
第2页，共59页，编辑于2022年，星期一
设F(i)表示从点A到达点i的最短距离，则55<299<300,因此更新）
第6次
389
300
299
170
第7次
389
300
299
170
158
第8次
389
300
299
170
158
65
第13页，共59页，编辑于2022年，星期一
思考？
有些同学可能会问:
对于每个f,为什么只保留一个数值呢?
而对于该序列，为什么要保留较大的值呢？
1. 再回过头来看方程:
f(i)=max{f(j)+1},其中j<i and a[j]>=a[i]
该式子表示找前面的一个最大f的符合条件的j,因此只要保存符合条件的最大的j就可以了。
在f值相同的情况下，保留较大的数显然更好。因为后面的数若能跟较小的数构成下降序列也一定能能较大的数构成下降序列，反之则不一定。例如207与300的f=2,但207不能与299构成下降序列，而300则可以。
因为生成的序列为有序序列，因此我们可以采用二分查找的方法很快查找到更新的值，时间复杂度为O(n㏒n)
第14页，共59页，编辑于2022年，星期一
求导弹的最小覆盖
第二问很容易想到贪心法：那就是采取多次求最长不上升序列的办法，然后得出总次数。
上述贪心法不正确，很容易就能举出反例。
例如： “7 5 4 1 6 3 2”
用多次求最长不上升序列所有为
“7 5 4 3 2”、“1”、“6”共3套系统；
但其实只要2套，分别为：
“7 5 4 1”与“6 3 2”。
那么，正确的做法又是什么呢？
第15页，共59页，编辑于2022年，星期一
分析
上述问题的原因是若干次最优决策值和不一定能推导出整个问题的最优。
为了解决这个问题下面介绍一个重要性质：
最少链划分=最长反链长度
为了证明这个性质，需要了解离散数学中偏序集的相关概念和性质以及偏序集的Dilworth定理。
第16页，共59页，编辑于2022年，星期一
偏序集
偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”），它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:
自反性：a≤a;
反对称性：如果a≤b且b≤a，则有a=b;
传递性：如果a≤b且b≤c，则a≤c 。
带有偏序关系的集合称为偏序集。
令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。
一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
一个链C是X的一个子集，它的任意两个元素都可比。
第17页，共59页，编辑于2022年，星期一
定理
在X中，对于元素a，如果任意元素b，都有a≤b，则称a为极小元。
定理1：令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。
第18页，共59页，编辑于2022年，星期一
证明：设p为最少反链个数
(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。
(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……，最终会有一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。
(3)因此r=p，定理1得证。
第19页，共59页，编辑于2022年，星期一
解决
要求最少的覆盖，按照Dilworth定理
最少链划分 = 最长反链长度
所以最少多少套系统 = 最长导弹高度上升序列长度。
知道了怎样求最长不上升算法，同样也就知道了怎样求最长上升序列。
时间复杂度O(n㏒n)。
第20页，共59页，编辑于2022年，星期一
青蛙过河(NOIP2005)
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥