资源描述：
《数论、组合数学与动态规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数论组合数学与动态规划莫梓元10年5月10年5月31日星期一例:NOIP99导弹拦截问题某国为了防御敌国的导弹袭击，研发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试验阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。第一个数据表示这套系统最多能拦截的导弹数；第二个数据表示若要拦截所有导弹至少要再添加多少套这样的系统。10年5月31日星期一补:PKU3636http://acm.pku.edu.cn
2、/JudgeOnline/problem?id=3636需要把一堆大小不同的玩具嵌套在一起，问最后最少剩几个玩具SampleInput4320304050304042030101030204050310302020301041010203040503951SampleOutput1210年5月31日星期一关于偏序集的DILWORTH定理最小链划分数等于最长反链长度最长上升子序列的长度等于不上升子序列的最小划分数其对偶定理也成立：上升子序列的最小划分数等于最长不上升子序列的长度10年5月31日星期一偏序集基础先介绍一下偏序关系：偏序是在
3、集合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不可比。10年5月31日星期一DILWORTH定理定理1令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。其对偶定理称为Dilwor
4、th定理：定理2令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。10年5月31日星期一定理证明证明：设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中极小元的集合
5、，从X2中删除A2得到X3……最终，会有一个Xk非空而X(k+1)为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。因此r=p，定理1得证。10年5月31日星期一结论：第一问：最长不下降子序列LISO(nlogn)第二问：由Dilworth定理可知，不上升子序列的最小划分数＝最长上升子序列的长度，复杂度同第一问。PKU3636方法同上，数据范围更大。10年5月31日星期一启发：HDU3335此题题面较
6、隐晦，容易被误导。正确解法因为套用Dilworth定理思想，使用最小路径覆盖（二分图匹配）解答。感谢daizhenyang同学原创。10年5月31日星期一例:PKU3731http://162.105.81.212/JudgeOnline/problem?id=3731给定一个矩形区域，人从左上角开始只允许前进或者右转且不允许越过矩形区域以及以前走过的路（即路径相交）。给定矩形右上角坐标和目标终点坐标，问有多少不同走法。10年5月31日星期一初步思路：由于只能不断右转，我们不不难发现可走的区域越来越小（左手边的区域不能走），这个特性为
7、动态规划提供了可能（无后效性？！），这是个很自然的思路但深入进去会发现状态和状态转移都无法清晰表示。打破局限，再仔细观察图例会发现终点两个相反对应方向的边数量相等或相差一，方向上相反。不妨枚举右转次数，这样可以确定每个方向上走过的次数。我们又知道每个方向上一共可走的路有多少条，这样很自然将思路转移向了排列组合。10年5月31日星期一排列组合右上角为（w,h），终点（x,y），step绕过的圈数，now为方向。四个不同方向间使用乘法原理，不同圈间使用加法原理。Cnm({h-y,w-x,y,x-1}(now),steps/4+steps%
8、4>now)递推预处理：Cnm=Cn-1m+Cn-1m-1注意细节！！（x=0,y=0,{h-y,w-x,y,x-1}<1)10年5月31日星期一例：生成树计数问题NOI07生成树计数一张无相图G有N个点，编号为i的点和
