Pi_F.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <time.h>
#include <string>
#include <vector>
#include <math.h>
#include <cassert>
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define ft first
#define sc second
#define mp make_pair
#define all(a) a.begin(), a.end()
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long li;
typedef long double ld;
typedef pair <li, li> pli;
typedef pair <int, int> pii;

using namespace std;

const int N = 100;

int n, k;
int a[N], b[N];
string sign[N];
long long dp[N][N];

enum {
    OLD,
    CUR,
    NEW
};

int F, S, L, R;

int get_type(int i) {
    if (i < L || i > R)
        return OLD;

    if (i == F || i == S)
        return CUR;

    return NEW;
}

bool compare(int a, int b, string s) {
    if (s == "=")
        return a == b;
    if (s == "<")
        return a < b;
    if (s == ">")
        return a > b;
    if (s == "<=")
        return a <= b;
    if (s == ">=")
        return a >= b;
}

bool is_good(int l, int r, int f, int s) {
    L = l, R = r;
    F = f, S = s;

    for (int i = 0; i < k; ++i) {
        int lf = get_type(a[i]);
        int rg = get_type(b[i]);

        if (lf != CUR && rg != CUR)
            continue;

        if (!compare(lf, rg, sign[i]))
            return false;
    }

    return true;
}

long long calcdp(int l, int r) {
    long long &res = dp[l][r];

    if (res != -1)
        return res;

    res = 0;

    if (l + 1 == r) {
        if (is_good(l, r, l, r))
            res++;
    } else {
        if (is_good(l, r, l, l + 1))
            res += calcdp(l + 2, r);
        if (is_good(l, r, l, r))
            res += calcdp(l + 1, r - 1);
        if (is_good(l, r, r - 1, r))
            res += calcdp(l, r - 2);
    }

    return res;
}

int main() {
    cin >> n >> k;

    n *= 2;
    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < k; ++i) {
        cin >> a[i] >> sign[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    cout << calcdp(0, n - 1);

    return 0;
}