(hdu step 1.3.6)Wooden Sticks(求長度和重量都嚴格遞增的數列的個數)

題目：

Wooden Sticks

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 2374 Accepted Submission(s): 921 Problem DescriptionThere is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:

(a) The setup time for the first wooden stick is 1 minute.
(b) Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l<=l' and w<=w'. Otherwise, it will need 1 minute for setup.

You are to find the minimum setup time to process a given pile of n wooden sticks. For example, if you have five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5), and (1,4), then the minimum setup time should be 2 minutes since there is a sequence of pairs (1,4), (3,5), (4,9), (2,1), (5,2).
InputThe input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n , 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains n 2 positive integers l1, w1, l2, w2, ..., ln, wn, each of magnitude at most 10000 , where li and wi are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
OutputThe output should contain the minimum setup time in minutes, one per line.
Sample Input

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

Sample Output

2
1
3

SourceAsia 2001, Taejon (South Korea)

題目大意：

給n根木棍的長度和重量。根據要求求出制作木棍的最短時間。建立第一個木棍需要1分鐘，若是接著要制作的木棍重量和長度都比此木棍長就不需要建立的時間，若是沒有，則再需要建立時間。求時間最小為多少。

題目分析：

一道貪心題，利用有序化數據進行貪心選擇。其實就是求長度和重量都嚴格遞增的數字序列的個數。

先按長度進行排序。排序完後的不一定都是下一根木棍重量和長度都大於前一根的。

代碼如下：

/*
 * f.cpp
 *
 *  Created on: 2015年1月29日
 *      Author: Administrator
 */

#include 
#include 
#include 


using namespace std;

const int maxn = 5005;

struct Node {
	int length;
	int weight;
	bool vis;
} node[maxn];

bool cmp(Node a, Node b) {
	if (a.length != b.length) {
		return a.length < b.length;
	}

	return a.weight < b.weight;
}

void printNodes(Node nodes[], int n) {
	int i;
	for (i = 0; i < n; ++i) {
		printf("(%d,%d)\n", nodes[i].length, nodes[i].weight);
	}
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);

		int i;
		for (i = 0; i < n; ++i) {
			scanf("%d%d", &node[i].length, &node[i].weight);
			node[i].vis = false;
		}

		sort(node, node + n, cmp);//先對數據進行排序

//		printNodes(node,n);//用來測試排序以後的數據序列

		int ans = 0;//最後的長度和重量都嚴格遞增的數列的個數

		int j;
		for (i = 0; i < n; ++i) {//遍歷這個數列中的每一個數

			if (node[i].vis == false) {//如果這一個數還沒有被訪問過
				node[i].vis = true;//那麼將這個鼠標紀委已經訪問
				ans++;//結果+1

				int weight = node[i].weight ;//標記當前的重量
				for (j = i + 1; j < n; ++j) {//掃描當前元素後面的所有元素
					//如果後面的元素沒有被訪問過&&後面的元素比當前元素的重量大 (因為排序以後長度默認已經是升序)
					if ((node[j].vis == false) && (node[j].weight >= weight)) {
						node[j].vis = true;//將該元素標記為已經訪問過
						weight = node[j].weight;//並且更新當前的重量值
					}
				}
			}

		}

		printf("%d\n", ans);
	}

	return 0;
}