LG P1020 导弹拦截 Dilworth

题目：

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出格式

输入格式：

一行，若干个整数（个数少于100000）

输出格式：

2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入输出样例

输入样例

389 207 155 300 299 170 158 65

输出样例

6
2

分析：

首先，了解一个定理。

Dilworth's Theorem:

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

An antichain in a partially ordered set is a set of elements no two of which are comparable to each other, and a chain is a set of elements every two of which are comparable. Dilworth's theorem states that there exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A. When this occurs, A must be the largest antichain in the order, for any antichain can have at most one element from each member of P. Similarly, P must be the smallest family of chains into which the order can be partitioned, for any partition into chains must have at least one chain per element of A. The width of the partial order is defined as the common size of A and P.

An equivalent way of stating Dilworth's theorem is that, in any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains. A version of the theorem for infinite partially ordered sets states that, in this case, a partially ordered set has finite width w if and only if it may be partitioned into w chains, but not less.

简单来说，这个定理说：一个任何反链最大元素数目等于任何将集合到链的划分中链的最小数目。

理解这个定理，这道题就非常ez了。简单动规马上过掉100%。但是洛谷加了一些非常恶心的数据，虽然开了SPJ，但我们必须要有迎难而上的精神啊x。

所以啊。利用一个简单的贪心算法来解决这个恶心的超时。

建立一个Tail数组，数组的值Tail[i]对应长度为i的最长不上升/下降子序列的尾端的坐标。如果当前数小于等于当前的最长不上升序列的结束点，那么我们把当前最长的不上升序列长度++，把当前数作为这个不下降序列的结束点，不然我们就用二分查找（显然它是又单调性的！），试着用当前数去更新长度为x的不上升序列的结束点。

程序：

100%算法非常简单。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAX = 100000 + 1;
 4 int n, Height[MAX], f[MAX];
 5 int main()
 6 {
 7     freopen("missile.in","r",stdin);
 8     freopen("missile.out","w",stdout);
 9     while (cin >> Height[++n])
10     {
11         continue;
12     }
13     n--;
14     for (int i = 1; i <= n; i++)
15     {
16         f[i] = 1;
17         for (int j = 1; j < i; j++)
18             if (Height[i] <= Height[j])
19                 f[i] = max(f[j]+1,f[i]);
20     }
21     int ans = 0;
22     for (int i = 1; i <= n; i++)
23         ans = max(ans,f[i]);
24     cout << ans << endl;
25     for (int i = 1; i <= n; i++)
26     {
27         f[i] = 1;
28         for (int j = 1; j < i; j++)
29             if (Height[i] > Height[j])
30                 f[i] = max(f[j]+1,f[i]);
31     }
32     ans = 0;
33     for (int i = 1; i <= n; i++)
34         ans = max(ans,f[i]);
35     cout << ans << endl;
36     return 0;
37 }

View Code

 1 // Data Strengthened
 2 // 200 Solution
 3 #include <bits/stdc++.h>
 4 using namespace std;
 5 const int MAX = 100000 + 1;
 6 int n = 0, Height[MAX], f[MAX], Tail[MAX], l, r, mid;
 7 int main()
 8 {
 9     freopen("missile.in","r",stdin);
10     freopen("missile.out","w",stdout);
11     while (cin >> Height[++n])
12     {
13         continue;
14     }
15     n--;
16     Tail[0] = 50000+1;
17     int ans = 0;
18     for(int i = 1; i <= n; i++)
19     {
20         if(Tail[ans] >= Height[i])
21         {
22             Tail[ans+1] = Height[i];
23             ans++;
24         }
25         else
26         {
27             l=0;
28             r=ans;
29             while(l<r)
30             {
31                 mid=(l+r)/2;
32                 if(Tail[mid] >= Height[i])
33                     l = mid+1;
34                 else
35                     r = mid;
36             }
37             if(l)
38                 Tail[l]=Height[i];
39         }
40     }
41     cout << ans << endl;
42     ans = 0;/*
43     for (int i = 1; i <= n; i++)
44     {
45         f[i] = 1;
46         for (int j = 1; j < i; j++)
47             if (Height[i] > Height[j])
48                 f[i] = max(f[j]+1,f[i]);
49     }
50     ans = 0;
51     for (int i = 1; i <= n; i++)
52         ans = max(ans,f[i]);
53     cout << ans << endl;*/
54     memset(Tail,-1,sizeof(Tail));
55     for(int i = 1; i <= n; i++)
56     {
57         if(Tail[ans] < Height[i])
58         {
59             Tail[ans+1] = Height[i];
60             ans++;
61         }
62         else
63         {
64             l=0;
65             r=ans;
66             while(l<r)
67             {
68                 mid=(l+r)/2;
69                 if(Tail[mid] >= Height[i])
70                     r = mid;
71                 else
72                     l = mid+1;
73             }
74             if(l)
75                 Tail[l]=Height[i];
76         }
77     }
78     cout << ans << endl;
79     return 0;
80 }