问题描述：
FatMouse相信：长得越胖的老鼠跑得越快。为了证明这是不对的，你需要搜集老鼠的数据。然后，在这些数据中选取一个尽可能大的子集，从而发现体重不断增长时，速度却不断下降。
输入
输入一群老鼠的资料，每只老鼠占一行。
每只老鼠的数据是一对整数：
第一个表示它的体重（克），第二个表示它的速度（厘米/秒），两个整数的范围是1～10000。
每组测试数据最多包含1000只老鼠的信息。
任何两只老鼠有可能体重相同，或速度相同，甚至体重和速度都完全相同。
输出
输出一系列数据；第一行是数字n；
接着有n行，每行是一个正整数（每个代表一只老鼠）。
如果这n个整数是m[1]，m[2]，…，m[n]，则必须满足：
W[m[1]]＜W[m[2]]＜…＜W[m[n]]
和 S[m[1]]＞S[m[2]]＞…＞S[m[n]]
为了确保答案是正确的，n应该尽可能的大。
所有的不等式都严格遵守约束：重量一定严格的逐渐增加，速度一定严格的逐渐减少。
可能有多种正确输出，你的程序只需输出其中一个：
本题为Special Judge。
算法分析：
- 因为有两个序列方向，直接应用最长单调递增子序列算法是不行的。
- 对数据进行预处理，首先按重量升序，重量相同时，按速度降序，然后对速度序列应用最长单调递增子序列算法。
1、样例分析
按重量升序，重量相同时，按速度降序后的排列后的结果如下图。
可以看出满足要求的序列最大长度是4。
在序号5、6和7的位置，三个重量都是6000，只能取一个速度。
在长度为4的情况下，显然答案有多组，所以是Special Judge：
① 4，5，2，1
② 4，5，2，7
③ 4，5，6，1
④ 4，5，6，7
⑤ …
2、数据结构
采用结构体表示老鼠的资料：
struct mouse {
//老鼠的重量、速度和编号int weight, speed, id;
} mice[1001];
老鼠的实际数量用变量n表示。
3、排序算法的实现
采用C语言的qsort()排序：
qsort(mice, n, sizeof(mouse), cmp);
其中cmp是排序因子。
在排序因子函数中，按老鼠的重量升序，在重量相同时，按速度降序。
//排序因子
int cmp(const void * a, const void * b)
{
mouse* ta = (mouse*) a;mouse* tb = (mouse*) b;if(ta -> weight == tb -> weight) //重量相同时return tb -> speed - ta -> speed; //按速度降序return ta -> weight - tb -> weight; //按重量升序
}
4、最长单调递增子序列算法的实现
实现时需要两个辅助数组：
① 存储构造到第i（1≤i＜n）个老鼠时，序列的最大长度：
int count[1001] = {
0};
②存储构造到第i（1≤i＜n）个老鼠时，序列的前驱：
int path[1001] = {
0};
//最长单调递增子序列算法
//下面是针对排序后的数组
int count[1001] = {
0}; //序列的最大长度
int path[1001] = {
0}; //序列的前驱
count[1] = 1;
for(int i = 2; i < n; i++)
{
for(int j = 1; j<i; j++)if(mice[i].weight>mice[j].weight && mice[i].speed<mice[j].speed)if(count[i] < count[j]) //得到了更长的序列{
count[i] = count[j];path[i] = j; //记录前驱}count[i]++;
}
//查找最大的序列长度
int max = 0; //最大长度
int pos; //最大长度元素所在位置
for(int i = 1; i < n; i++)if(count[i] > max){
max = count[i];pos = i;}
//输出最大长度
printf("%d\n", max);
5、输出子序列的序号
首先查找最大的序列长度，也就是在数组count中查找最大值max，并记录该最大值所在的位置pos。
- 根据位置pos，在数组path中递归输出就可以了。
- 如果当前位置是pos，则前一个位置是path[pos]。
- 采用递归算法，刚好确保从前往后的顺序输出。
//输出子序列序号的算法
void output(int path[], int pos)
{
if(pos == 0) return;output(path, path[pos]);printf("%d\n", mice[pos].id);
}
