俄罗斯套娃程序

题目:

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 **二维数组的使用, 基数排序.