在写题解之前给自己打一下广告哈~。。抱歉了，希望大家多多支持我在CSDN的视频课程，地址如下：
题目：
FatMouse’s Speed
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1034 Accepted Submission(s): 526
Problem Description
FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.
Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.Two mice may have the same weight, the same speed, or even the same weight and speed.
Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],…, m[n] then it must be the case thatW[m[1]] < W[m[2]] < … < W[m[n]]andS[m[1]] > S[m[2]] > … > S[m[n]]In order for the answer to be correct, n should be as large as possible.All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.
Sample Input
6008 13006000 2100500 20001000 40001100 30006000 20008000 14006000 12002000 1900
Sample Output
44597
Source
Zhejiang University Training Contest 2001
Recommend
Ignatius
题目分析：
简单DP。求最长上升子序列。只不过这道题“在第一关键字升序的情况下,根据第二关键字来求最长下降子序列”，，并且需要输出路径。为了达到序列根据第一关键字升序,所以这个时候我们需要对序列进行以下排序。
代码如下：
/* * d1.cpp * * Created on: 2015年2月10日 *Author: Administrator */#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int maxn = 1005;struct Mouse{int weight;//用来记录老鼠的重量int speed;//用来记录老鼠的速度int len;//用来记录到目前为止的最长上升子序列的长度int id;//用来标记这个老鼠原本的idint pre;//用来标记最长上升子序列中当前索引的上一个索引…}mouse[maxn];int cnt;bool cmp(const Mouse& a,const Mouse& b){if(a.weight != b.weight){return a.weight < b.weight;//根据重量升序}return a.speed < b.speed;//在重量相同的情况下,根据质量升序}/** * 最长上升子序列的核心算法。 * 这里返回的是最长上升子序列的最后一个数的索引。 * 而不直接返回最长上升子序列的长度, * 因为这道题还需要把最长上升子序列的路径输出. * 有了索引就很容易吧路径输出… */int LIS_Len(){int i;int j;int maxIndex = -1;//全聚德最长上升子序列的最后一位的索引.用于输出LIS的长度和路径int max = -99;//用于标记全局的最长上升子序列的长度for(i = 0 ; i < cnt ; ++i){//第一层遍历:从头到尾遍历每一个数int temp = 0;//用于计算到当前这个索引为止的最长上升子序列的长度for(j = 0 ; j < i ; ++j){//第二层遍历:遍历到当前这个索引的前一个索引。用于求到目前这个索引为止的最长上升子序列的长度及路径if(mouse[j].weight < mouse[i].weight && mouse[j].speed > mouse[i].speed){//如果能够成一个符合要求的序列(最长上升子序列)//if( mouse[j].speed > mouse[i].speed){//虽然这种写法也能AC.很明显这种写法对数据的约束不够强。不能处理weight相同,speed的不同的情况if(temp < mouse[j].len){//如果到索引j的最长上升子序列的长度>目前的最长上升子序列的长度temp = mouse[j].len;//更新到目前为止所能达到的最长上升子序列的长度mouse[i].pre = j;//记录索引i的前一个索引是j}}}mouse[i].len = temp+1;//更新到索引i是所能达到的最长上升子序列的长度。到索引i所能达到的最长上升子序列的长度=到索引i的前一个索引j时所能达到的最长上升子序列的长度+1if(max < mouse[i].len){//如果到i所能达到的最长上升子序列的长度>目前的全局的上升子序列的长度max = mouse[i].len;//更新全局的最长上升子序列的长度maxIndex = i;//距离全局的最长上升子序列的最后一个元素的索引}}return maxIndex;//返回全局的最长上升子序列的最后一个元素的索引}/** * 用于输出最长上升子序列的路径 */void output(int k){if(mouse[k].len == 1){//如果这已经是LIS的第一个元素了printf("%d\n",mouse[k].id);//直接输出他的ID}else{//如果不是output(mouse[k].pre);//先输出前面的元素的IDprintf("%d\n",mouse[k].id);//在输出自己的ID}}int main(){while(scanf("%d%d",&mouse[cnt].weight,&mouse[cnt].speed)!=EOF){mouse[cnt].len = 1;mouse[cnt].id = cnt+1;//因为最后输出结果时,第一个元素是从1开始比较的.而我们从索引0开始计数cnt++;}cnt -= 1;sort(mouse,mouse+cnt,cmp);//先让序列按weight升序int maxIndex = LIS_Len();printf("%d\n",mouse[maxIndex].len);output(maxIndex);return 0;}
一个能从别人的观念来看事情，能了解别人心灵活动的人，永远不必为自己的前途担心。
