题目:
C++:
#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
bool cmp(int *p, int *q)
{
if(p[0] == q[0]) return p[1] < q[1];
else return p[0] < q[0];
}
int main(void)
{
int n = 0;
cin>> n;
int **a = new int*[n];
for (int i = 0; i < n; ++i) {
a[i] = new int[2];
cin>>a[i][0];
cin>>a[i][1];
}
sort(a, a + n, cmp);
int res[n];
memset(res, 0, sizeof(res));
int ans = 0;
for(int i = 0; i < n; i++){
if(res[i] == 0){
int h = a[i][0];
int w = a[i][1];
int last = i;
for(int j = i + 1; j < n; j++){
if(a[j][0] > h && a[j][1] > w){
res[j] = res[last] + 1;
last = j;
h = a[j][0];
w = a[j][1];
}
}
ans = max(ans, res[last] + 1);
}
}
cout<<ans<<endl;
delete a;
a = NULL;
return 0;
}
注意对int **二维数组的使用, 基数排序.
