misteriouspresent.cc

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct C {
    int x, y;

    bool operator<(const C & o) const {
        return x < o.x && y < o.y;
    }

    void print() {
	printf("c: %d %d\n", x, y);
    }
};

vector<C> cards;

vector<vector<int>> state;

int solve_table() {
    for(int t = 0; t < cards.size(); ++t) {
        state[cards.size()][t] = 0;
    }
    for(int i = cards.size()-1; i >=0; --i) {
        for(int t = 0; t < cards.size(); ++t) {
            int x = 0;
            if(cards[t] < cards[i]) {
                x = 1 + state[i+1][i];
            }
            int y = state[i+1][t];
            state[i][t] = max(x, y);
        }
    }
    return state[1][0];
}

int solve(int i, int t) {
    if(i >= cards.size()) return 0;

    int x = 0;
    printf("solve %d %d\n", i, t);
    cards[t].print();
    cards[i].print();
    if(cards[t] < cards[i]) {
        printf("fit %d %d\n", i, t);
        x = 1 + solve(i+1, i);
    }
    int y = solve(i+1, t);
    return max(x, y);
}

int main() {
    int N;
    cin >> N;
    cards.resize(N+1);

    for(int i = 0; i <= N; ++i) {
        cin >> cards[i].x >> cards[i].y;
    }
    sort(cards.begin()+1, cards.end());
    state.assign(N+2, vector<int>(N+1, 0));

    int r = solve_table();
    printf("%d\n", r);
    printf("%d\n", solve(1, 0));

}