戳我看原题

40TLEcode:

#include <bits/stdc++.h>
using namespace std;

bool vis[5001];
int n, sum, cnt = 0;

struct wood {
	int l, w;
} a[5001];

struct maxlong {
	int ml, nex;
} dp[5001];

bool a_contain_b(wood a, wood b) {
	return a.l >= b.l && a.w >= b.w;
}

void check(int x) {
	dp[x].ml = 0;
	while (dp[x].nex) 
		vis[dp[x].nex] = true, dp[x].nex = dp[dp[x].nex].nex;
	for (x = 1; x <= n; x++) {
		while (vis[dp[x].nex])
			dp[x].nex = dp[dp[x].nex].nex, dp[x].ml--;
	}
}

int main() {
	memset(vis, 0, sizeof(vis));
	scanf("%d", &n);
	sum = n;
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].l, &a[i].w);
		dp[i].ml = 1, dp[i].nex = 0;
	}
	sort(a + 1, a + n + 1, a_contain_b);
	for (int i = n - 1; i > 0; i--)
		for (int j = n; j > i; j--)
			if (a_contain_b(a[i], a[j]) && dp[i].ml < dp[j].ml + 1)
				dp[i].ml = dp[j].ml + 1, dp[i].nex = j;
	int x = 0;
	while (sum) {
		for (int i = 1; i <= n; i++)
			if (dp[i].ml >= dp[x].ml)
				x = i;
		cnt++;
		sum -= dp[x].ml;
		check(x);
	}
	printf("%d\n", cnt);
	return 0;
}