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