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\n",dp[0][0]); 47 return 0; 48 }
原文：https://www.cnblogs.com/letlifestop/p/10978330.html