codeforces 567 F. Mausoleum (dp)
很容易看出来是dp
我们左右一起，一对一对放．
对于每一对，有三种方法，分别是两左，一左一右，两右．
初始区间长度为２n，每次放完后缩小区间长度 ，最后一定是放２个n，这个时候区间长度缩小为２，表明一种满足题意的情况．
状态转移的时候需要分别判断三个状态是否满足题目中给出的k组限制条件．
细节见注释．
/*************************************************************************
> File Name: code/cf/#314/F.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月16日 星期日 14时37分15秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x7fffffff;
24const int N = 1E2+7;
25int n, k, a[N], b[N];
26LL dp[N][N];
27string sign[N];
28int L, R, F, S;
29enum
30{
31 OLD, CUR, NEW
32};
33int get_type(int i)
34{
35 if (i < L || i > R) return OLD;
36 if (i == F || i == S) return CUR;
37 return NEW;
38}
39bool compare(int a, int b, string s)
40{
41 if (s == "=") return a == b;
42 if (s == ">") return a > b;
43 if (s == "<") return a < b;
44 if (s == ">=") return a >= b;
45 if (s == "<=") return a <= b;
46}
47bool check(int l, int r, int f, int s)
48{
49 L = l, R = r;
50 F = f, S = s;
51 for (int i = 0; i < k; i++)
52 {
53 int lf = get_type(a[i]); // 判断对于当前要添加的位置，是否有题目中给出限制的位置，如果是，判断是否满足限制．
54 //如果有一个限制条件不满足就不成立，所有限制条件都满足才成立．
55 int rg = get_type(b[i]);
56 if (lf != CUR && rg != CUR) continue;
57 if (!compare(lf, rg, sign[i])) return false;
58 }
59 return true;
60}
61LL cal(int l, int r)
62{
63 LL &res = dp[l][r];//dp[l][r] 表示在区间[l,r]放置的方案的个数
64 if (res != -1) return res;
65 res = 0;
66 if (l + 1 == r) //最后相邻，表示最后两个n放在一起了，答案＋１
67 {
68 if (check(l, r, l, r)) res++;
69 } else
70 {
71 if (check(l, r, l, l + 1)) res += cal(l + 2, r); //一对的两个都放在左边
72 if (check(l, r, l, r)) res += cal(l + 1, r - 1); //左１右１
73 if (check(l, r, r - 1, r)) res += cal(l, r - 2);// 右２
74 }
75 return res;
76}
77int main ()
78{
79 scanf("%d %d", &n, &k);
80 n = n * 2;
81 for (int i = 0; i < k; i++)
82 {
83 cin>>a[i]>>sign[i]>>b[i];
84 a[i]--;
85 b[i]--;
86 }
87 memset(dp, -1, sizeof(dp));
88 printf("%I64d\n",cal(0,n-1));
89 return 0;
90}