题意：
有 n 根木棒，长度和质量都已经知道，需要一个机器一根一根地处理这些木棒。
该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。
机器需要的准备时间如下：
1.第一根需要1min的准备时间；
2.在加工了一根长为 l ，重为 w 的木棒后，接着加工一根长为 l’（l <= l’），重为 w’
（w <= w’）的木棒是不需要任何准备时间的，否则需要1min时间。
求加工 n 根木棒所用的最少时间。例如现有长和重分别为（4,9），（5,2），（2,1），（3,5）和（1,4）
的5根木棒，那么所需的最少时间为2min，顺序为（1,4），（3,5），（4,9），（2,1），（5,2）；
分析：
属于资源调度问题，贪心算法能获得很好的效率。
但仅用贪心还是不够的，排序后还要用动态规划
方法一：
排序后求上升子序列的最少组数，这个组数即最少时间。
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct mu
{
int L,W;
} m[];
bool cmp(mu a, mu b)
{
if(a.L == b.L) //优先按长度排序，相等时按重量
return a.W < b.W;
else
return a.L < b.L;
}
int main()
{
int t;
int b[]; //记录第 i 个木棒的分组序号
cin >>t;
while(t--)
{
memset(b, , sizeof(b));
int n;
cin >>n;
for(int i = ; i < n; i ++)
scanf("%d%d", &m[i].L, &m[i].W);
sort(m, m + n, cmp);
b[] = ; //第一个分为第一组
for(int i = ; i < n; i ++) //依次为后面的木棒分组
{
int k = ;
for(int j = ; j < i; j ++) //在当前木棒前面的木棒中找到比它沉且组数为最大的
if(m[i].W < m[j].W && k < b[j])
k = b[j];
b[i] = k + ; //当前木棒分为第 k + 1 组
}
int ma = ;
for(int i = ; i < n; i ++) //最大组数即最少时间
if(b[i] > ma)
ma = b[i];
cout <<ma <<endl;
}
return ;
}
方法二：
分组，只记录每组第一个，标记为0，其余的标记为1.
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
struct mu
{
int l, w;
} m[];
bool cmp(mu a, mu b)
{
if(a.l == b.l)
return a.w < b.w;
else
return a.l < b.l;
}
int main()
{
int t, n;
int b[];
cin >>t;
while(t --)
{
memset(b, , sizeof(b));
scanf("%d", &n);
for(int i = ; i < n; i ++)
scanf("%d%d", &m[i].l, &m[i].w);
sort(m, m + n, cmp);
for(int i = ; i < n; i ++)
{
if(b[i] == )
continue; //已分组，看下一个
int k = m[i].w; //本组第一个
for(int j = i + ; j < n; j ++)
{
if(b[j] == )
continue;
if(m[j].w >= k) //后面升序的都归为本组
{
k = m[j].w;
b[j] = ;
}
}
}
int cnt = ;
for(int i = ; i < n; i ++)
if(b[i] == )
cnt ++;
printf("%d\n", cnt);
}
return ;
}