最近在学习算法，于是在网上找了一些题目练手。这篇是的ACM的一个题目，名字叫“心急的c小加”。
题目是这样的：
心急的C小加
- 描述
-
C小加有一些木棒，它们的长度和质量都已经知道，需要一个机器处理这些木棒，机器开启的时候需要耗费一个单位的时间，如果第i+1个木棒的重量和长度都大于等于第i个处理的木棒，那么将不会耗费时间，否则需要消耗一个单位的时间。因为急着去约会，C小加想在最短的时间内把木棒处理完，你能告诉他应该怎样做吗？
- 输入
- 第一行是一个整数T(1<T<1500)，表示输入数据一共有T组。
每组测试数据的第一行是一个整数N（1<=N<=5000）,表示有N个木棒。接下来的一行分别输入N个木棒的L，W（0 < L ,W <= 10000），用一个空格隔开，分别表示木棒的长度和质量。 - 输出
- 处理这些木棒的最短时间。
- 样例输入
-
3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1
- 样例输出
-
2 1 3
下面是我从网上查到后自己总结的解题思路：
1）首先对输入的所有木棒按长度和重量进行从小到大的排序（先排长度，长度相同再排重量）
2）获得一个有序的序列之后，再从这个序列中找出有多少个子序列，就表示需要处理多少次，要花多少个单位时间了
3）比如： 输入是
4 9 5 2 2 1 3 5 1 4
这一组共有5个，排完序应是这样的（1 4）（2 1）（3 5） （4 9） （5 2）
再从这个5个里面找出子序列，步骤如下：
a. （1 4）是第一个，需要花一个单位时间处理，（1 4）是一个子序列 ， 我们叫它序列1
b. （2 1）进来，在他前面没有比他小的（长度和重量都小），如是（2 1）也是一个子序列，我们叫它序列2
c. （3 5）进来，它比前面的（1 4） 和（2 1）都大，随便选一个（默认是第一个），于是把它放到序列1， 这时候序列1是（1 4） （3 5）
除此之外还要用（3 5）替代（1 4）来跟后面的比较，因为只要后面的比（3 5）大那它肯定也比（1 4）大【例（4 6）】，但如果
它不比（3 5）大但比（1 4）大 【例 （4 4）】就可以看作序列1是（1 4） （4 4），然后(3 5) 单独做序列3。其效果是一样的，只不过序列1的内容不同
d. （4 9）进来，它比前面的 (3 5) 大，如果把它放到序列1，这时候序列1 是 （1 4） （3 5） （4 9），同时 （4 9）替代（3 5）跟后面的比较
e. （5 2）进来，它比前面的（4 9）小，但比（2 1）大，如是把它放到序列2，这时候序列2 是 （2 1） （5 2），并用（4 2）替代（2 1）跟后面的比较
综上所述，最后一共有2个子序列 ：
（1 4） （3 5） （4 9） 和 （2 1） （5 2）
比较序列就是这2个子序列各自的最后一个元素（ 4 9） 和 （5 2）
所以处理时间一共就是2.
下面的是根据以上的思路写出来的C++代码
#include"iostream"
#include "stdlib.h"
#include "algorithm"
using namespace std;
class stick
{
public:
int length;
int weigth;
public:
stick()
{
length=0;
weigth=0;
}
stick(int l,int w)
{
length=l;
weigth=w;
}
bool operator < (const stick& s) const
{
return s.length>length || (s.length==length &&s.weigth>weigth);
}
};
int main()
{
int n;
cin>>n;
int dp[5000][2]; //用来存放比较序列元素
while(n--)
{
int m;
cin>>m;
stick *s =new stick[m];
int l,w;
int i;
for(i=0;i<m;i++)
{
cin>>l>>w;
s[i]=stick(l,w);
}
sort(s,s+i);
int sum=0; //子序列的个数，即比较序列的个数
int flag; //标志位，非0表示在比较序列中找到了比当前元素小的
for(int i=0;i<m;i++) //外层循环是遍历所有的元素
{
flag=0;
for(int j=0;j<sum;j++) //内层循环遍历所有的待比较元素
{
if(s[i].length>=dp[j][0] && s[i].weigth>=dp[j][1] && !flag)
{
dp[j][0]=s[i].length; //如果新的元素比比较序列中的大，就替代它
dp[j][1]=s[i].weigth; flag=1;
}
}
if(!flag) //如果新元素比待比较序列中的都小，则单独做为一个子序列（子序列数+1，同时比较序列多一个元素）
{
dp[sum][0]=s[i].length;
dp[sum][1]=s[i].weigth;
sum++;
}
}
cout<<sum<<endl;
}
return 0;
}