CF div2 D. Neko and Aki's Prank //dp+greedy

CF div2  D. Neko and Aki's Prank //dp+greedy

题意： 给你一颗字典树，包括所有的括号组合（左括号多余或等于右括号），求最多的连边数（任意两条边没有公共定点）。

先知道什么是字典树（trie），很直观的一个东西 

这是一颗字典树，能够表示abc，abd，acb这三个单词。

因为左右括号可以匹配，所以可以记录很多相同的状态，所以维护dp[高度][左括号-右括号的数量]的节点数，然后直接从上向下转移。

知道每一层的总括号后，因为每一个父节点比能找到一个儿子节点，联立删除，所以直接贪心从上面往下面删点，求答案。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 1e9+7;
const int max_n =1e5+5;
int dp[2005][2005];//第几层，几个多的l

int main(){
    int n;scanf("%d",&n);
    dp[0][0]=1;
    int ans=0;
    for(int i=0;i<n*2;i++){
        for(int j=0;j<=i+1;j++){
            int ll=(i-j)/2+j;
            if(ll<n) dp[i+1][j+1]+=dp[i][j],dp[i+1][j+1]%=mod;
            if(j>0)  dp[i+1][j-1]+=dp[i][j];dp[i+1][j-1]%=mod;
        }

    }
    int del=0;
    for(int i=0;i<n*2;i++){
        int x=(-del+mod)%mod;
        for(int j=0;j<=i;j++){
            x=(x+dp[i][j])%mod;
        }
        del=x;
        ans=(ans+x)%mod;
    }
    printf("%d",ans);
    return 0;
}