Untitled

 avatar
unknown
plain_text
2 years ago
899 B
3
Indexable
#include <iostream>
using namespace std;

int max(int a, int b)
{
    return (a > b) ? a : b;
}

int sol(int n, int i, double A[], double B[], int C[])
{
    if (i == n - 1)
    {
        C[i] = 1;
    }

    for (int j = i + 1; j < n; j++)
    {
        int temp = (A[i] < A[j] && B[i] > B[j]) ? 1 : 0;

        if (C[j] != 0)
        {
            C[i] = max(temp + C[j], C[i]);
        }
        else
        {
            C[i] = max(temp + sol(n, j, A, B, C), C[i]);
        }
    }

    return C[i];
}

int main()
{
    int t;
    cin >> t;

    for (int j = 0; j < t; j++)
    {
        int n;
        cin >> n;

        double A[n], B[n];
        int C[n];

        for (int i = 0; i < n; i++)
        {
            cin >> A[i];
            cin >> B[i];
            C[i] = 0;
        }

        cout << sol(n, 0, A, B, C) << "\n";
    }
}
Editor is loading...