题解 CF1152D 【Neko and Aki's Prank】
ljc20020730
2019-04-25 11:25:43
[CF 1152 Solution ](https://www.cnblogs.com/ljc20020730/p/10766001.html)
考虑一个长度为2n ($n \leq 1000$)的括号序列所在的字典树，一组合法的选边是任取一条边两端的两个点都不在边集中其他边中出现。
最大化选边集合的边数。 由于答案较大，对$10^9 + 7 $取模.
Solution :
考虑到括号序列所在的trie树，若两个括号序列前缀平衡数一定的时候，那么为了保证最后得到合法的括号序列，那么显然，其子树必然相等。
显然，我们不需要重复计算这些冗余的量。
考虑维护这个状态 ， 考虑到确定一个等价的状态只需要确定当前序列总长度和当前平衡值即可。
我们这里对于当前括号序列平衡值的定义是：当前左括号数-右括号数。
显然，通过这两种状态就可以确定一些相互等价的点。这些状态的数目是$n^2$
考虑一个简单的dp，设$f[i][j]$表示当前括号序列长度为$i$（深度），左括号数-右括号数（平衡值）
考虑转移：
$ f[i][j] += f[i-1][j-1] $新增1个右括号
$ f[i][j] += f[i-1][j+1] $新增1个左括号
我们需要知道转移是否合法，即能否组成新的边，这取决于父亲节点$(i-1)$的合法性。
不妨设$g[i][j]$为$f[i][j]$意义下对于$(i,j)$的合法性 ，
转移也非常显然 $g[i][j] = !(g[i-1][j-1]||g[i-1][j+1])$
所以若$ g[i][j] = 1$ 时 生成(i,j) 的方案会额外多1种。
所以转移方程可以写成
$ f[i][j] = f[i-1][j-1] + f[i-1][j+1] + g[i-1][j-1]||g[i-1][j+1]$
$ g[i][j] = !(g[i-1][j-1]||g[i-1][j+1])$
边界 $f[0][0]=0, g[0][0] = 1$
细节方面直接对于一个$ f[i][j] $显然需要满足$j \leq i$。
Code :
```cpp
# include <bits/stdc++.h>
# define int long long
const int N=2e3+10;
const int mo=1e9+7;
int f[N][N]; bool g[N][N];
using namespace std;
signed main()
{
int n; scanf("%lld",&n); n<<=1;
f[0][0]=0,g[0][0]=true;
for (int i=1;i<=n;i++)
for (int j=0;j<=n;j++)
{
int ret=0,flag=0;
if (j!=0) ret=(ret+f[i-1][j-1])%mo,flag|=g[i-1][j-1];
if (j+1<=i-1) ret=(ret+f[i-1][j+1])%mo,flag|=g[i-1][j+1];
if (flag) f[i][j]=(ret+1)%mo,g[i][j]=false;
else f[i][j]=ret%mo,g[i][j]=true;
}
printf("%lld\n",f[n][0]);
return 0;
}
```