Codeforces Round #554 (Div. 2) D题 Neko and Aki's Prank （记忆化dfs）

题目链接：http://codeforces.com/contest/1152/problem/D

题意：给定一个数字n，构造一个长度为2n的括号序列，每个‘（ ’都能在其右边找到唯一对应的‘ ）’则为合法序列，根据所有合法情况建一棵树，现有一个边集S满足集合内所有边均无公共点，求该边集的最大值（对1e9+7取模）

思路：从前三个样例就可以发现，只要保证间隔的边都取就一定会得到最大的边集，那么接下来就是如何建树，直接dfs按树扫所有边集大小，但是这样会t，那么就记忆化它，开一个dp[1000][1000][2]的数组记录已遍历过的值，dp[i][j][k]表示已经取了i个左括号和j个右括号且最后一个括号节点的状态为k（k为1表示该节点已经在边集S中，k为0表示该节点还没取过）

代码：

#include<iostream>
#include <cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<functional>
#include <unordered_map>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 50;
const int mod = 1e9 + 7;
ll dp[maxn][maxn][2];
int n;
ll dfs(ll a, ll b, ll k)
{
ll ans = 0;
if (dp[a][b][k])
return dp[a][b][k];
int c = k;
if (a < n)
{
int tmp = k ? 0 : 1;
ans += dfs(a + 1, b, tmp) + tmp;
ans %= mod;
k = 1;
}
if (a > b)
{
int tmp = k ? 0 : 1;
ans += dfs(a, 1 + b, tmp)+tmp;
ans %= mod;
}
dp[a][b][c] = ans%mod;
return ans%mod;
}
int main()
{
scanf("%d", &n);
memset(dp, 0, sizeof(dp));
ll ans;
ans = (1+dfs(1, 0, 1))%mod;
printf("%lldn",ans);
}

最后

以上就是秀丽篮球为你收集整理的Codeforces Round #554 (Div. 2) D题 Neko and Aki's Prank （记忆化dfs）的全部内容，希望文章能够帮你解决Codeforces Round #554 (Div. 2) D题 Neko and Aki's Prank （记忆化dfs）所遇到的程序开发问题。

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