ZOJ 1025 Wooden Sticks (DP)

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1025

如果我们定义在一个sticks序列中，对所有的 j>i 均满足 : sticks[i].l>=sticks[j].l 且 sticks[i].w>=sticks[j].w ，则称这个序列为一个 “簇”。本题就是求把所有的元素分为最少的簇数。

假设输入为A，首先把A排序（按 l 的增序，若两个元素的 l 相同，则按 w 的增序），排序后的序列称为B，对序列B按照元素的属性 w 求最长递减子序列的长度（严格递减），记为len。则我们要求得最少簇数就等于 len 。

最长递减子序列的动态规划方法详见我的另一篇博客：http://www.cnblogs.com/TenosDoIt/archive/2013/04/19/3031589.html

下面我们证明最少簇数 cu 等于 len：

将最长递减子序列记为C，则C中的元素满足C[i].l>=C[j].l && C[i].w<C[j].w ( 其中 i<j )，他们不满足簇的性质。因此最长递减子序列中的len个元素必定每个都分布在不同的簇中，因此最少的簇数为len。

代码如下：

 1 #include<iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct node
 7 {
 8     int l;
 9     int w;
10 };
11 
12 bool comp(struct node a,struct node b)
13 {
14     if(a.l==b.l)
15         return a.w<b.w;
16     else return a.l<b.l;
17 }
18 
19 
20 int main()
21 {
22     int caseNum;
23     cin>>caseNum;
24     while(caseNum--)
25     {
26         int N;
27         vector<node> sticks;
28         cin>>N;
29         for(int i=1;i<=N;++i)
30         {
31             node tmp;
32             cin>>tmp.l>>tmp.w;
33             sticks.push_back(tmp);
34         }
35         sort(sticks.begin(),sticks.end(),comp);
36 
37         int *F=new int[N+1];
38         int result=0;
39         F[0]=1;
40         for(int i=1;i<N;i++)
41         {
42             F[i]=1;
43             for(int j=0;j<i;j++)
44             {
45                 if(sticks[i].w<sticks[j].w)
46                     F[i]=max(F[i],F[j]+1);
47             }
48             
49             if(F[i]>result)
50                 result=F[i];  
51         }
52         delete []F;
53         cout<<result<<endl;
54     }
55     return 0;
56 }