DP:Wooden Sticks(POJ 1065)

　　　　　　　　　　　　　　　　摆木棍

　　题目大意：即使有一堆木棍，给一个特殊机器加工，木棍都有两个属性，一个是l一个是w，当机器启动的时候（加工第一根木棒的时候），需要一分钟，在这以后，设机器加工的上一根木棒的长度是l，质量是w，下一次加工的木棒长度为l`,质量为w`，当且仅当l`>=l且w`>=w时，机器不需要额外的时间，否则还需要一分钟重新启动，问你最短的加工时间？

　　下面介绍两个方法：

　　方法一，直接贪心法：

　　这个方法的原理是：因为我们总是想把更多的木棍按序排列，所以我们可以先把一个属性先排列了，再考虑另一个属性，那么这样的话假设我们先排序l，那么的话我们就只用看w就可以了，但是在我第一次想的时候我犯了一个很严重的错误，那就是我把w也按照升序来操作了（而没有跟新当前最大质量），实际上我们还要更新stick的最大质量，这样才能行（当然要used域了）

　　还要注意的是排序的时候当l相等的时候，w记得按照升序排

　　代码太简单了，我不贴了，反正这算法跑挺慢的，我写的跑47ms，没啥意思，我们来点有意思的方法。

　　方法二：LIS（最长下降子序列）

　　在扯这个方法之前，我们先来讲一下组合数学的东西：偏序集和Dilworth定理

　　偏序集的定义：

　　设一个集合P，里面满足关系R，设xRy表示x与y满足R相关，x!Ry表示x与y不相关

　　1.如果对于X中的所有元素x,都有x与x满足R的关系，那么则说明R是自反的

　　2.如果对于X中的所有元素x,都不满足R的关系（x!Rx），那么说明R是反自反的。

　　3.如果对于X所有的x和y，都有xRy,x!Ry，则说明R是反对称的，否则如果xRy和xRy成立时，x!=y则说明R是对称的

　　4.如果X所有元素xyz,满足xRy,yRz，如果一定存在xRz，则说明R是传递的

　　偏序集就是一个自反，反对称且传递的关系，偏序是一种关系（比如集合的包含，大于小于都是偏序，特别的，一切不带等号的偏序都是严格偏序）

　　现在我们直接用偏序集的定理（不证），详细证明方法看维基百科https://en.wikipedia.org/wiki/Dilworth%27s_theorem

　　偏序集的定理1：

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

　　偏序集的定理2：（DilWorth定理）

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

　　也就是链的最小化划分数=反链的最大长度

　　参考http://blog.csdn.net/xuzengqiang/article/details/7266034

　　那么说到这里，你就明白了，这一题其实就是最著名的LIS（只不过他是要求反链）

　　LIS有两个解法，各有优劣，第一个解法虽然是O（n^2），但是可以显示出所有的链长和回溯显示链

　　第一个解法其实就是DP，我们从头到尾搜索数组，不断更新当前位置的最长长度（当然这个要满足下降关系），然后找出最长的链就可以了，很简单

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 typedef struct woods_
 7 {
 8     int length;
 9     int weight;
10 
11 }WOODS;
12 typedef int Position;
13 int fcomp(const void *a, const void *b)
14 {
15     if ((*(WOODS *)a).length != (*(WOODS *)b).length)
16         return (*(WOODS *)a).length - (*(WOODS *)b).length;
17     else
18         return (*(WOODS *)a).weight - (*(WOODS *)b).weight;
19 }
20 
21 static WOODS woods_set[10000];
22 static int dp[10000];
23 
24 void Search(const int);
25 
26 int main(void)
27 {
28     int case_sum, woods_sum;
29     scanf("%d", &case_sum);
30     for (int i = 0; i < case_sum; i++)
31     {
32         scanf("%d", &woods_sum);
33         for (int j = 0; j < woods_sum; j++)
34             scanf("%d%d", &woods_set[j].length, &woods_set[j].weight);
35 
36         qsort(woods_set, woods_sum, sizeof(WOODS), fcomp);
37         memset(dp, 0, sizeof(dp));
38         if (woods_sum == 0)
39             printf("0
");
40         else Search(woods_sum);
41     }
42     return 0;
43 }
44 
45 void Search(const int woods_sum)
46 {
47     int ans = 1;
48 
49     dp[0] = 1;
50     for (int i = 1; i < woods_sum; i++)
51     {
52         dp[i] = 1;
53         for (int j = 0; j < i; j++)
54         {
55             if (woods_set[j].weight > woods_set[i].weight)
56                 dp[i] = max(dp[j] + 1, dp[i]);
57         }
58     }
59     ans = 0;
60     for (int i = 0; i < woods_sum; i++)
61         ans = max(ans, dp[i]);
62     printf("%d
", ans);
63 }

　　第二个方法是O(nlogn)，这个很快，原理就是我们的最长连储存就可以了，然后用二分的方法更新元素，并且用贪婪的方法，不断更新stacks里面的元素（比如我们按照从大到小排，那么不断更新最大就可以了），让链的增长潜能变大！这个方法的缺点就是不能显示链（显示的也是错的），而且只能找最长的那一条。

　　不过为什么这个算法能成立也是很有趣的，因为我们一直在更新元素，但是最后的链的序不一定就是原来的序，其实内在的原因就是这个方法把每一个元素都等价了，其实不管我们怎么找，如果我们只用找最长的话，那么其实我们只用把潜力变大？（下降链找最大元素，上升链找最小元素），那么这样的链的长度最后一定是最大的

　　代码：

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 typedef struct woods_
 7 {
 8     int length;
 9     int weight;
10 
11 }WOODS;
12 typedef int Position;
13 int fcomp(const void *a, const void *b)
14 {
15     if ((*(WOODS *)a).length != (*(WOODS *)b).length)
16         return (*(WOODS *)a).length - (*(WOODS *)b).length;
17     else
18         return (*(WOODS *)a).weight - (*(WOODS *)b).weight;
19 }
20 
21 static WOODS woods_set[10000];
22 static int stacks[10000];
23 
24 void Search(const int);
25 Position Binary_Search(const int,int,int,const int len);
26 
27 int main(void)
28 {
29     int case_sum, woods_sum;
30     scanf("%d", &case_sum);
31     for (int i = 0; i < case_sum; i++)
32     {
33         scanf("%d", &woods_sum);
34         for (int j = 0; j < woods_sum; j++)
35             scanf("%d%d", &woods_set[j].length, &woods_set[j].weight);
36 
37         qsort(woods_set, woods_sum, sizeof(WOODS), fcomp);
38         //memset(stacks, -1, sizeof(stacks));
39         if (woods_sum == 0)
40             printf("0
");
41         else Search(woods_sum);
42     }
43     return 0;
44 } 
45 
46 Position Binary_Search(const int goal, int left, int right, const int len)
47 {
48     int mid;
49 
50     while (left <= right && left != len)//二分法维护序列
51     {
52         mid = (left + right) / 2;
53         if (goal < stacks[mid])
54             left = mid + 1;
55         else
56             right = mid - 1;
57     }
58     return left;
59 }
60 
61 void Search(const int woods_sum)
62 {
63     int pos, len = 0;
64 
65     stacks[0] = -1;
66     for (int i = 0; i < woods_sum; ++i)
67     {
68         pos = Binary_Search(woods_set[i].weight, 0, len, len);
69 
70         stacks[pos] = woods_set[i].weight;
71         if (pos == len)
72             len++;
73     }
74     printf("%d
", len);
75 }