codeforces 1152 D. Neko and Aki's Prank（最大匹配||dp）

http://codeforces.com/contest/1152/problem/D

题意：给出一个n，n个括号组成过程的字典树，选出最多的边数，使得选的所有边无共同顶点。

自己没想出来，大概知道转移方程，但不知道怎么取边最优…
思路：从叶子节点开始取，每取一条边，就把该叶子节点与父节点删除，然后一直取到最上边即为最优情况。因为题目的特殊性，每个叶子节点深度相同，我们只需要取每两层的总节点数的最小节点数目即可，那么进一步思考，由于括号要合法，左括号一定要大于右括号，由于奇数层之前会出现完全匹配状态,那么有一部分只能添加左括号，所以一定奇数层更少，所以直接将奇数层添加情况求和。

定义dp[i][j] i为深度，j为左括号减右括号数目，转移就由上一层数目转移过来
初始dp[0][0]=1；
注意考虑边界情况，j<=n的同时 j的数目要与对应深度情况合法，不能大于该层次最大的左括号减右括号数目

#include<bits/stdc++.h>
#define fi first
#define se second
#define log2(a) log(n)/log(2)
#define show(a) cout<<a<<endl;
#define show2(a,b) cout<<a<<" "<<b<<endl;
#define show3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> LP;
const ll inf = 1e17 + 10;
const int N = 2e6 + 10;
const ll mod = 1e9+7;
const int base=131;
const double pi=acos(-1);
map<string, int>ml;
map<ll,ll> mp;
map<int,int> vi;
ll b[N], vis[N], num[N], po[N],t, n, m, x, y,res, k,a[N];
ll ans,cnt;
vector<ll> v;
string s;
ll dp[2005][1005];
int main( )
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
dp[0][0]=1;
for(int i=1;i<=2*n;i++)
{
for(int j=0;j<=2*n-i&&j<=n;j++)
{
dp[i][j]=(dp[i-1][j+1]+(j > 0 ? dp[i-1][j-1] : 0))%mod;
num[i]=(num[i]+dp[i][j])%mod;
}
}
for(int i=1;i<=2*n;i+=2)
{
ans=(ans+num[i])%mod;
}
cout<<ans;
}

最后

以上就是畅快小蘑菇为你收集整理的codeforces 1152 D. Neko and Aki's Prank（最大匹配||dp）的全部内容，希望文章能够帮你解决codeforces 1152 D. Neko and Aki's Prank（最大匹配||dp）所遇到的程序开发问题。

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