D. Neko and Aki's Prank（DP）

题目链接：

https://codeforces.com/contest/1152/problem/D

题目大意：

给你一个n，你是能够构造出一个长度为2*n的合法括号序列，然后把这些括号序列构造成一个字典树的形式，每一次操作你可以对一条边染色。染完色之后，和这条边相邻的边都不能被染色。

然后问你这棵树最多能染多少条这样的边。

具体思路：

结论一：把这颗树构造出来之后，会发现相邻的两个叉构成的边，染色之后是互补的。

结论二：对于当前的一个节点，我们定义 ans=（左括号的数量 - 右括号的数量）。当ans 相同的时候，以这个点为根节点的子树中，对答案的贡献是相同的。

所以我们每一次贪心的对这个树形结构从下往上对一个点进行染色，如果当前点的两个子节点都没有染色，就把这个点给染上色。

dp[i][j] 表示在这个树形结构的第i层，ans值为j的时候，对答案的贡献是多少

AC代码：

 1 #pragma comment(linker, "/STACK:102400000,102400000")
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 # define ll long long
 5 # define inf 0x3f3f3f3f
 6 # define ll_inf (1ll<<60)
 7 # define lson l,mid,rt<<1
 8 # define rson mid+1,r,rt<<1|1
 9 const int maxn = 2e3+10;
10 const int  N = 15;
11 const int mod = 1e9+7;
12 int dp[maxn][maxn];
13 int vis[maxn][maxn];
14 int main()
15 {
16     int n;
17     scanf("%d",&n);
18     for(int i=2*n-1; i>=0; i--)
19     {
20         for(int j=0; j<=2*n-1; j++)
21         {
22             int flag=1;
23             if(j-1>=0)
24             {
25                 dp[i][j]=(dp[i][j]+dp[i+1][j-1])%mod;
26                 if(vis[i+1][j-1]==0)
27                 {
28                     flag=0;
29                 }
30             }
31             if(j+1<=2*n-i-1)
32             {
33                 dp[i][j]=(dp[i][j]+dp[i+1][j+1])%mod;
34                 if(vis[i+1][j+1]==0)
35                 {
36                     flag=0;
37                 }
38             }
39             if(flag==0)
40             {
41                 vis[i][j]=1;
42                 dp[i][j]=(dp[i][j]+1)%mod;
43             }
44         }
45     }
46     printf("%d
",dp[0][0]);
47     return 0;
48 }