wikioi--1044 拦截导弹

题目链接：http://www.wikioi.com/problem/1044/

题目其实就是最长上升子序列的变形。

下面是两个重要定理：

定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。其对偶定理称为Dilworth定理：

定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

这样问题的第一问是问一套系统最多能拦截多少个导弹，题目意思是每次不能超过上一次的高度，那么也就是求序列中最长不上升的子序列，代码中用的是O(n^2)的经典算法。

第二问呢，最少得要多少套系统才能拦截所有导弹，根据定理，最长上升子序列的长度对应的就是反链的最少个数，也就是最少的系统数。

代码实现采用的是O(nlogn)的算法，http://www.slyar.com/blog/longest-ordered-subsequence.html

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <ostream>
 8 #include <vector>
 9 #include <list>
10 using namespace std;
11 
12 vector<int> data;
13 int dp1[10000];
14 int dp2[10000];
15 int main()
16 {
17     int tmp;
18     while(scanf("%d",&tmp)!=EOF)
19     {
20         data.push_back(tmp);
21     }
22     int n = data.size();
23     dp1[0] = 1;
24     int ans = 1;
25     int i;
26     for(i = 1; i < n ; ++i)
27     {
28         int _max;
29         _max = 0;
30         for(int j = 0 ; j < i ; ++j)
31         {
32             if(data[j] > data[i])
33             {
34                 _max = max(_max,dp1[j]);
35             }
36         }
37         dp1[i] = _max+1;
38         ans = max(ans,dp1[i]);
39     }
40     cout<<ans<<endl;
41 
42     //O(nlogn)的算法求最长上升子序列
43     ans = 0;
44     dp2[0] = -1;
45     for(i = 0 ; i < n ; ++i)
46     {
47         if(data[i] > dp2[ans])
48         {
49             dp2[++ans] = data[i];
50         }
51         else
52         {
53             int low = 1;
54             int high = ans;
55             int mid;
56             while(low <= high)
57             {
58                 mid = (low + high)/2;
59                 if(data[i] > dp2[mid])
60                 {
61                     low = mid+1;
62                 }
63                 else
64                 {
65                     high = mid-1;
66                 }
67             }
68             dp2[low] = data[i];
69         }
70     }
71     cout<<ans<<endl;
72     return 0;
73 }