题目链接：

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

下面是两个重要定理：

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

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

 

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

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

代码实现采用的是O(nlogn)的算法，

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 using namespace std;11 12 vector
              
                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<
               
                <
                
                  dp2[ans])48 {49 dp2[++ans] = data[i];50 }51 else52 {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 else64 {65 high = mid-1;66 }67 }68 dp2[low] = data[i];69 }70 }71 cout<
                 
                  <