zju2283 -- challenge of wisdom.cpp

Zhejiang University Online Judge 第2277题至第2283题的代码和解题报告

// PROB         Zju Online Judge 2283 -- Challenge of Wisdom
// Algorithm    Math + Longest Increasing Sub Sequence
// Complexity   O (n Log n)
// Author       LoveShsean
#include <stdio.h>
#include <algorithm>

#define maxn 100100
#define inf 2147483647

using namespace std;

typedef struct { int x, y; } Tpoint;

int N, M, P;
Tpoint d [maxn];
int b [maxn], ans;

int cmp (const Tpoint &a, const Tpoint &b)
{
 	return (a.x > b.x || a.x == b.x && a.y > b.y);
}

void solve ()
{
 	int i, j, t;
 	sort (d, d + P, cmp);
 	b [ans = 0] = -inf;
 	for (i = 0; i < P; i ++)
 	{
 	 	t = d [i].y;
 	 	j = std :: lower_bound (b, b + ans + 1, t) - b;
 	 	if (j > ans) b [++ ans] = t;
 	 	else if (t < b [j]) b [j] = t;
 	}
}

int main ()
{
 	int i;
 	while (scanf ("%d%d%d", &N, &M, &P) == 3)
 	{
 	 	for (i = 0; i < P; i ++) scanf ("%d%d", &d [i].x, &d [i].y);
 	 	solve ();
 	 	printf ("%d\n", ans);
 	}
 	return 0;
}