MCARDS - Card Sorting

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
using namespace std;

int p[] = {0, 1, 2, 3}, c, n;
struct card {
	int col, val;
	bool operator < (const card &o) const {
		return col != o.col ? p[col] < p[o.col] : val < o.val;
	}
} a[444], last[444];

void enter() {
	scanf("%d%d", &c, &n);
	for(int i = 0; i < c * n; ++i) {
		scanf("%d%d", &a[i].col, &a[i].val);
		--a[i].col;
	}
}

void solve() {
	int res = n * c;
	do {
		int maxlen = 0;
		for(int i = 0; i < c * n; ++i) {
			int dp = lower_bound(last, last+maxlen, a[i]) - last;
			if(dp >= maxlen) last[maxlen++] = a[i];
			else last[dp] = min(last[dp], a[i]);
		}
		res = min(res, n * c - maxlen);
	} while (next_permutation(p, p+c));
	printf("%d\n", res);
}

int main() {
	enter();
	solve();
	return 0;
}

Download