Neko is playing with his toys on the backyard of Aki's house. Aki decided to play a prank on him, by secretly putting catnip into Neko's toys. Unfortunately, he went overboard and put an entire bag of catnip into the toys...

It took Neko an entire day to turn back to normal. Neko reported to Aki that he saw a lot of weird things, including a trie of all correct bracket sequences of length 2n.

The definition of correct bracket sequence is as follows:

  • The empty sequence is a correct bracket sequence,
  • If s is a correct bracket sequence, then (s) is a correct bracket sequence,
  • If s and t are a correct bracket sequence, then st is also a correct bracket sequence.
    For example, the strings "(())", "()()" form a correct bracket sequence, while ")(" and "((" not.

Aki then came up with an interesting problem: What is the size of the maximum matching (the largest set of edges such that there are no two edges with a common vertex) in this trie? Since the answer can be quite large, print it modulo 1e9+7.

链接🔗
[CodeForces 1152D]Neko and Aki's Prank

题解
DP + 二分图思想
先按 DP[i][j] 进行动态规划
DP[i][j] 表示前i个符号,还有j个左括号为匹配的合法方案数
然后求最大匹配点,将树抽象成二分图,左边放奇数层点,右边放偶数层点,偶数层点一定比奇数层点大,所以最大匹配为奇数层点

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxd =  2e3+10;
const ll mod  = 1e9+7;
ll dp[maxd][maxd],n;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    cin >> n;ll ans = 0; dp[0][0] = 1;
    for(int i=1;i<=2*n;i++)
    {
        for(int j=0;j<=i&&j+i<=2*n;j++)
        {
            if(j) (dp[i][j] += dp[i-1][j-1])%=mod;
            (dp[i][j] += dp[i-1][j+1])%=mod;
            if(i&1) (ans += dp[i][j]) %=mod;
        }
    }
    cout << ans;
    return 0;
}