Poj 1065: Wooden Sticks

poj1065.md

Poj 1065: Wooden Sticks

題目

分析

真想不到啊…竟然是 LIS

題解參 這

另外，這題是 Dilworth's theorem 的應用。

AC Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <queue>

using namespace std;

struct Stick {
	int l;
	int w;
	
	bool operator < (const Stick& s) const {
		if (l != s.l)
			return l < s.l;
		return w < s.w;
	}
};

int N;
Stick sticks[5000];
int dp[5000];

int solve() {
	sort(sticks, sticks + N);
	
	// O(n^2)
	// fill(dp, dp + N, 1);
	// for (int i = 0; i < N; i++) {
	// 	for (int j = 0; j < i; j++) 
	// 		if (sticks[j].w > sticks[i].w)
	// 			dp[i] = max(dp[i], dp[j] + 1);
	// }
	
	// return *max_element(dp, dp + N);
	
	// O(nlgn)
	fill(dp, dp + N, -1);
	for (int i = 0; i < N; i++) {
		*lower_bound(dp, dp + N, sticks[i].w, greater<int>()) = sticks[i].w;
	}
	
	return lower_bound(dp, dp + N, -1, greater<int>()) - dp;
}

int main() {
	int T;
	scanf("%d", &T);
	
	while (T--) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
			scanf("%d %d", &sticks[i].l, &sticks[i].w);
		
		printf("%d\n", solve());
	}
	
	return 0;
}