codeforces1152D. Neko and Aki's Prank DP

题目链接 嗷！！！！

求n对括号组成的正确序列的字典树的最大匹配

大概是传说中树形DP。
记DP[i][j]为用了i个括号，左括号与右括号个数的差j，即将长度与差值相同的状态合并。这样i对应与树的深度，sum dp[i][] 为深度为i时节点的个数
从叶节点开始匹配，为每一个叶节点找一个匹配，再跳到下一层可以接受匹配的位置，并为这一层中每一个节点找一个匹配，重复直到到达根节点。

#include <stdio.h>
#include <climits>
#include <cstring>
#include <time.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <vector>
#include <string>
#define INF 0x3f3f3f3f
#define ll long long
#define Pair pair<int,int>
#define re return
#define getLen(name,index) name[index].size()
#define mem(a,b) memset(a,b,sizeof(a))
#define Make(a,b) make_pair(a,b)
#define Push(num) push_back(num)
#define rep(index,star,finish) for(register int index=star;index<finish;index++)
#define drep(index,finish,star) for(register int index=finish;index>=star;index--)
using namespace std;
const int mod=1e9+7;
const int maxn=2048;
int N;
ll dp[maxn][maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>N;
dp[1][1]=1;
rep(dep,1,2*N){
rep(dif,0,min(2*N-dep,dep)+1){
if(dif<N){
dp[dep+1][dif+1]+=dp[dep][dif];
dp[dep+1][dif+1]%=mod;
}
if(dif>0){
dp[dep+1][dif-1]+=dp[dep][dif];
dp[dep+1][dif-1]%=mod;
}
}
}
ll ans=0;
for(register int dep=2*N-1;dep>0;dep-=2){
rep(dif,0,min(2*N-dep,dep)+1){
ans+=dp[dep][dif];
ans%=mod;
}
}
cout<<ans<<endl;
re 0;
}

最后

以上就是鳗鱼外套为你收集整理的codeforces1152D. Neko and Aki's Prank DP的全部内容，希望文章能够帮你解决codeforces1152D. Neko and Aki's Prank DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。