这篇文章讲的很好了，我把自己理解的过程再记录一下。
回想了一下好像与最长递增子序列有些联系。有木有联系这个坑待填。
--------------------------
之前曾经分析过最长递增子序列（那篇Blog还在施工中...-->现在施工完毕了）
========================
先补充一些偏序方面的知识：
偏序关系：
偏序是在集合X上的二元关系≤，它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:
自反性：a≤a;
反对称性：如果a≤b且b≤a，则有a=b;
传递性：如果a≤b且b≤c，则a≤c 。
带有偏序关系的集合称为偏序集。
当a与b之间存在a≤b或b≤a时，称a与b可比。
一个反链A是X的一个子集，它的任意两个元素都不可比。
一个链C是X的一个子集，它的任意两个元素都可比。
单个元素的偏序集是链。这我自己的推论，应该对吧。。
偏序定理：
定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
回到1065，这题就是要找出树枝集合的最小数目的划分，每个划分的子集都是链。链内部按顺序排列链内部没有setup开销，链之间有setup开销。
这可以保证机器的setup时间最少。由于上面的定理，可以知道，这种最小数目的划分为最长反链的长度。也就是要找出一个集合，这个集合保证包含了最多的两两之间不可比的元素【最长的反链】。
考虑本题具体条件下的一个反链：
{a,b,c,d}；a,b,c,d都不可比。
假如对a,b,c,d按l排序的顺序为 a.l < c.l = d.l < b.l;由于不可比，a.w > c.w > d.w > b.w。
方法1：那本题就转化为，在l升序排列下求w的最长递减子序列。
补上本法的代码：
#include <stdio.h>
#include <algorithm>
#define N 5000
using namespace std;
typedef struct _ws{
int l;
int w;
}ws;
ws s[N];
bool cmp(ws a,ws b){
return a.l < b.l;
}
int main(){
int t,n,i,j,Len;
scanf("%d",&t);
while(t > 0){
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%d%d",&s[i].l,&s[i].w);
}
sort(s,s+n,cmp);
int D[N+1];//可改为O(nlgn) 长度为n的DS（decrease subsequence）的最大结尾
D[1] = s[0].w;j = 1;Len = 1;//求w的最长严格递减子序列
while(j < n){
if(s[j].w < D[Len]){
D[++Len] = s[j].w;
}
// else if(s[j].w == D[Len]){
// ;//do nothing
// }
else{
int k = Len;
while(k > 0){
if(s[j].w < D[k])
break;
k--;//O(n^2)
}
D[k+1] = s[j].w;
}
j++;
}
printf("%d\n",Len);
t--;
}
return 0;
}
poj1065测试通过.
方法2：另外也想出了一个方法用图的方法解决之。
先根据每个点的关系做一个哈塞图，接着按类似拓扑排序的“减治法”找出所有的反链，接着得出最长的反链元素个数+1即是本题的答案.
==以后有空再写这个方法的代码。