记录编号	43459	评测结果	AAAAA
题目名称	木棍	最终得分	100
用户昵称	临轩听雨ゐ	是否通过	通过
代码语言	C++	运行时间	0.177 s
提交时间	2012-10-10 19:02:17	内存使用	3.33 MiB

#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
ifstream in("wooden.in");
ofstream out("wooden.out");
int n,m;
int l[5010]={0},w[5010]={0};
int f[5010]={0};

void sort(int aa,int bb)
{
    int i=aa,j=bb;
	int a=l[(i+j)/2];
	int b=w[(i+j)/2];
	while (i<j){
		while (l[i]<a||(l[i]==a&&w[i]<b)) i++;
		while (l[j]>a||(l[j]==a&&w[j]>b)) j--;
		if (i<=j)
		{
			int tmp;
			tmp=l[i];l[i]=l[j];l[j]=tmp;
			tmp=w[i];w[i]=w[j];w[j]=tmp;
			i++,
			j--;
		}
	}
	if (aa<j) sort(aa,j);
	if (i<bb) sort(i,bb);
}

int main()
{
    int ans=0;
    in>>n;
    
    for (int i=1;i<=n;i++)
    {
        in>>l[i]>>w[i];
        f[i]=1;
    }
    
    sort(1,n);
    
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<i;j++)
            if (w[j]>w[i]&&f[i]<f[j]+1)
               f[i]=f[j]+1;
        ans=max(f[i],ans);
    }
    out<<ans<<endl;
    return 0;
}