关于偏序集与dilworth。【拦截导弹题解】
看了好久好久，终于看懂了。
于是果断发一篇。 尽量讲得易懂点吧。
【第一篇学术讨论文~~】
首先，二元关系的定义：
设S是一个非空集合，若R是关于S的有序元素对的一个关系，即对S中任意一个有序元素对（a，b），我们总能确定a与b是否满足条件R，就称R是S的一个关系（relation），又由于他是建立在二元（即S中任意两个元素）之上的，因此也称为二元关系。
然后，偏序关系的定义：
偏序关系是在集合X上的二元关系 “≤”（这只是个抽象符号，其内涵是由你定义的，并不是“小于或等于”），它满足自
反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:
自反性：a≤a; 【自我反对称，大概就是这个意思吧】
反对称性：如果a≤b且b≤a，则有a=b;
传递性：如果a≤b且b≤c，则a≤c 。
偏序关系与一般二元关系的区别，也就在于其三个性质
例如集合S={a1，a2...an},设其每一个表示一个人
如果二元关系为【a为男，b为女】，那么这个二元关系显然不符合第一条性质自反性，因此这是二元关系而不是偏序关系。
又如二元关系为【a是b的亲戚】，那么这个二元关系显然不符合第二条性质反对称性，因此这是二元关系而不是偏序关系。
又如二元关系为【a认为b是好人】，那么这个二元关系显然不符合第三条性质传递性，因此这是二元关系而不是偏序关系。
于是偏序关系介绍到这里。
偏序集：也就是带有偏序关系的集合。偏序集可以表示为集合与偏序关系的整体，记为（X,≤）【其中X为集合，≤为偏序
关系】。对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比，这就是可比性的定义。
一个链C是X的一个子集，它的任意两个元素都可比。
极小元：在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。很容易看出，在链中，极小元可以看做链的初始元，
有点类似于拓扑图中没有前驱的点。
相对应的，一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
至于最大链，最大反链，就是集合中最长【即包含元素最多】的链、反链的意思了。
而最大反链数，就是一个集合最多可以划分成多少个反链。最长反链长度就是最长反链中元素个数。
下面，两个重要定理，有关dilworth：
定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则r为X的最大反链数。
对偶定理:定理2：对于一个偏序集，其最少反链划分数等于其最长链的长度。这就是Dilworth定理。
定理2证明：首先设p为最少反链划分个数。
因为划分成反链以后，反链中间任何两个元素都不可比，因此最大链中的元素必须全部分开，因此必然有p大于等于r。【为
了避免与偏序关系的符号重复，在此使用中文“大于等于”等等进行说明】
下面证明r大于等于p：
设X1=X，考虑这样一种操作，第i次操作从Xi中拿出其所有最小元的集合，设为Ai。那么总存在k，使得第k次操作前的Xk为非
空集合而X（k+1）为空集。此时每次拿出的最小元集合顺序为A1,A2...Ak ，易知这就是X种反的一链划分。由于每次取出的
都是最小元，由最小元的定义我们可以得知，对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。由此A1...Ak中一定
存在一条链【有人说有反例，哼哼，你们试试吧】。又因为r是最长链长度，因此r大于等于k，又易知k要大于等于p，因此r
大于等于p。
综上所述，r=p，得证。
有了这个，定理1也就很好证明了【过程类似嘛】，请读者自行证明。【其实是因为我很懒，嘿嘿】
现在我们再来看拦截导弹
【Description 描述】
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到
达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶
段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截
所有导弹最少要配备多少套这种导弹拦截系统。
【Input 输入文件】missile.in
单独一行列出导弹依次飞来的高度。
【Output 输出文件】missile.out
两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数
【Sample Input输入样例】
389 207 155 300 299 170 158 65
【Sample Output输出样例】
6
2
第一问很好做，最长不上升子序列。
第二问，哈哈，往上翻~上翻~，这不是求最少链划分数嘛？这不是反的Dilworth吗？
那也就是说，既然最少反链划分数等于其最长链的长度，那最少链划分数不就是最大反链长度吗？
恭喜你答对了。于是问题一下子转化成了求最大反链长度。反过来dp一次，马上ac
注意一点，由于在此题中链的定义是“a≤b→a出现在b之前且a大于等于b”
因此反链是“a出现在b前且a小于b（不能等于啊！）”
欢迎大神鄙视...
Copyright © 2007
2024年1月16日 20:37
I really enjoy reading and also appreciate your work
2024年9月12日 16:16
Instantly this web site will irrefutably frequently end up being notable regarding all weblog consumers, due to diligent reviews as well as checks
2024年9月12日 16:44
Well-Written article. It will be supportive to anyone who utilizes it, including me. Keep doing what you are doing – can't pause to read more posts. Thanks for the precious help
2024年9月12日 17:14
Loving the information on this site, you have done great job on the content . This looks absolutely perfect. All these tinny details are made with lot of background knowledge. I like it a lot. This was a useful post and I think it is rather easy to see from the other comments as well that this post is well written and useful. I am definitely enjoying your website. You definitely have some great insight and great stories. As I website possessor I think the content material here is really good , thankyou for your efforts.
2024年9月12日 17:17
I really like your style. Thanks a million and please keep up the effective work. it was a wonderful chance to visit this kind of site and I am happy to know. thank you so much for giving us a chance to have this opportunity .
2024年9月12日 17:20
Bought it for the first time, Love it! The deliver speed is fast and the customer service is great. Will buy again.
2024年9月12日 17:24
I was wanting to know if you could write a litte more on this subject? I’d be very thankful if you could elaborate a little bit further. Bless you!
2024年9月12日 17:26
I visit your blog regularly and recommend it to all of those who wanted to enhance their knowledge with ease. The style of writing is excellent and also the content is top-notch. Thanks for that shrewdness you provide the readers!
2024年9月12日 17:27
This is very interesting content! I have thoroughly enjoyed reading your points and have come to the conclusion that you are right about many of them. You are
2024年9月12日 17:28
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks...
2024年9月12日 17:28
I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much.
2024年9月12日 17:30
At the point when I at first remarked I seem to have tapped on the - Notify me when new remarks are added-checkbox and now every time a remark is added I get four messages with a similar remark. There must be a simple strategy you can eliminate me from that assistance? Much
2024年9月12日 17:32
wow! Thanks! I continually wanted to write on my website online some thing like that. Am i able to encompass a portion of your post to my website? Have you ever puzzled who posts a number of these items that you come upon?
2024年9月12日 17:35
I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often
2024年9月12日 17:35
I read a article under the same title some time ago, but this articles quality is much, much better. How you do this.. Wonderful blog post. This is absolute magic from you! I have never seen a more wonderful post than this one. You've really made my day today with this. I hope you keep this up! You completed a number of nice points there. I did a search on the issue and found nearly all people will have the same opinion with your blog
2024年9月12日 17:35
I want you to thank for your time of this wonderful read !!! I definately enjoy every little bit of it and I have you bookmarked to check out new stuff of your blog a must read blog
2024年9月12日 17:36
I'm glad to discover such huge numbers of valuable information here in the post. we need work out more methods in such manner. a debt of gratitude is in order for sharing.
2024年9月12日 17:36
I came to this site with the introduction of a friend around me and I was very impressed when I found your writing. I'll come back often after bookmarking!
2024年9月12日 17:38
Bought it for the first time, Love it! The deliver speed is fast and the customer service is great. Will buy again.
2024年9月12日 17:38
I am so pleased I situated your blog site, I actually situated you by mistake, while I was taking a look at on google for another point, Anyways I am below now in addition to additionally would certainly just like to insist give thanks to for an outstanding blog post along with an all-around entertaining internet site. Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has the same topic with your article. Thanks, great share
2024年9月12日 17:39
I came to this site with the introduction of a friend around me and I was very impressed when I found your writing. I'll come back often after bookmarking!
2024年9月12日 17:43
Hello, I really enjoyed reading your post. Actually I'm doing something similar to yours. You and I have a lot in common. Like you, I have posted a lot of articles on my website. If you are interested, please visit and read. Thank you. Have a nice day.
2024年9月12日 17:58
Really amazing post. I just stumbled beside your blog. I will definitely suggest your blog to all of my friends. Thanks for sharing this valuable information for free
2024年9月12日 18:07
I wanted to thank you for this great read!! I definitely enjoying every little bit of it I have you bookmarked to check out new stuff you post
2024年9月12日 18:47
Hello from LeadsMax.biz!! We are shutting down and have made all our data available for all the countries! Come check us out and search your business and consumer data for free LeadsMax.biz