itdef

地址 https://www.papamelon.com/problem/327

由于題目有兩個排序關鍵字長度和重量，只有兩個均大于等于前一個才能達到最小費用
先嘗試按照某一個關鍵字排序
例子中的
4 5 2 3 1
9 2 1 5 4
排序后就變成
1 2 3 4 5
4 1 5 9 2

這時候我們就發現 排序后 第二行的關鍵字 按照最長不下降子序列切分后 就是最小費用了
比如說
1 3 4
4 5 9
但是如何得知最后能得到最少幾組最長不下降序列？
這里就涉及到Dilworth定理

Dilworth定理：
通俗解釋： 把一個數列劃分成最少的最長不降子序列的數目就等于這個數列的最長下降子序列的長度（LIS)。
也就是solve2的解法 直接求最長下降子序列的長度。

//=========================================

solve3 貪心解法
按照以下思路進行解答
木棒有兩個關鍵字屬性 l=長度 w=重量。 木棒已經按照l進行排序
1 在已有的不降子序列中尋找序列尾部小于等于當前木棒w的序列，該序列是尋找出的序列中尾部最大的那個，在該序列尾部插入該木棒
2 如果沒有找到合適的不降子序列 則新開一個序列。
3 持續 1 2過程 直到所有木棒都插入序列 序列個數則是答案

證明貪心解就是最優解
假設貪心解不是最優解答 另有最優解
那么在最優解和貪心解 在第一個木棒插入序列不同點之后的插入序列，都可以經過有限次調整進行互換。即，貪心解與最優解可以經過有限次調整進行互換，也就是相等。
那么貪心解就是最優解。

代碼見solve3

代碼

 
#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

const int N = 5010;
const int INF = 9999999;

struct STICK {
	int l;
	int w;
}stick[N];

int n, t;

bool cmpFunc(const struct STICK& a, const struct STICK& b) {
	if (a.l < b.l) return true;
	else if(a.l==b.l) return a.w < b.w;

	return false;
}

void solve() {
	int ans = 0; 
	for (int i = 0; i < n; i++) {
		if (stick[i].w != INF) {
			int curr = -INF;
			for (int j = i; j < n; j++) {
				if (curr == -INF && stick[j].w != INF) {
					curr = stick[j].w; ans++;
				}
				else if (stick[j].w != INF && curr <= stick[j].w) {
					curr = stick[j].w; stick[j].w = INF;
				}
			}
		}
	}

	cout << ans << endl;
	return;
}

void solve2() {
	int dp[N]; memset(dp, 0, sizeof dp);
	dp[0] = 1;
	int ans = 0;
	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		for (int j = i - 1; j >= 0; j--) {
			if (stick[i].w < stick[j].w) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(ans, dp[i]);
	}

	cout << ans << endl;

	return;
}

void solve3() {
	int up[N]; int cnt = 0;
	for (int i = 0; i < n; i++) {
		int curr = -INF; int idx = -1;
		for (int j = 0; j < cnt; j++) {
			//找到up中小于等于 stick[i].w中最大的數 ， 在其代表的序列中插入stick[i].w
			//找不到則新建一個序列 插入stick[i].w
			if (up[j] <= stick[i].w && curr < up[j]) {
				idx = j; curr = up[j];
			}
		}
		if (idx != -1) {
			up[idx] = stick[i].w;
		}
		else {
			up[cnt] = stick[i].w; cnt++;
		}
	}

	cout << cnt << endl;
	return;
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n;
		memset(stick,0,sizeof stick);

		for (int i = 0; i < n; i++) {
			cin >> stick[i].l >> stick[i].w;
		}
		sort(stick,stick+n,cmpFunc);

		//solve();
		//solve2();
		solve3();
	}



	return 0;
}