(hdu step 3.2.4)FatMouse's Speed(在第一關鍵字升序的情況下,根據第二關鍵字來求最長下降子序列)

 

題目：

 

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 DescriptionFatMouse 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. InputInput 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 that

W[m[1]] < W[m[2]] < ... < W[m[n]]

and

S[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 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Sample Output

4
4
5
9
7

  SourceZhejiang University Training Contest 2001 RecommendIgnatius

 

題目分析：

簡單DP。求最長上升子序列。只不過這道題“在第一關鍵字升序的情況下,根據第二關鍵字來求最長下降子序列”，並且需要輸出路徑。為了達到序列根據第一關鍵字升序,所以這個時候我們需要對序列進行以下排序。

 

代碼如下：

 

/*
 * d1.cpp
 *
 *  Created on: 2015年2月10日
 *      Author: Administrator
 */

#include 
#include 
#include 



using namespace std;

const int maxn = 1005;

struct Mouse{
	int weight;//用來記錄老鼠的重量
	int speed;//用來記錄老鼠的速度
	int len;//用來記錄到目前為止的最長上升子序列的長度
	int id;//用來標記這個老鼠原本的id
	int 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時所能達到的最長上升子序列的長度+1

		if(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
,mouse[k].id);//直接輸出他的ID
	}else{//如果不是
		output(mouse[k].pre);//先輸出前面的元素的ID
		printf(%d
,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
,mouse[maxIndex].len);
	output(maxIndex);


	return 0;
}