提高A组模拟简单的序列

wjh15101051's space

卧薪尝胆，厚积薄发。

提高A组模拟简单的序列

Date: Sun Aug 12 16:08:23 CST 2018

In Category: NoCategory

Description：

有个括号序列 $s$ ，满足 $|s|=m$ 。统计括号序列对 $(p,q)$ 的数量。其中 $(p,q)$ 满足 $|p| + |s| + |q| = n$ ，且 $ p + s + q $ 是一个合法的括号序列。

$1\le n\le 2000$

Soltuion：

我的做法： $f[i][j]$ 表示 $i$ 个括号，两两匹配后还能剩 $j$ 个括号，每次枚举最前面的合法的括号序列长度并用卡塔兰数算方案数转移 $O(n^3)$ ，不可前缀和优化，不可数据结构优化。得分 $75$ 。

正解： $f[i][j]$ 表示 $i$ 个左括号 $j$ 个右括号的方案数 $(i\ge j)$ ，转移时枚举最后一个左括号右边的右括号个数 $k$ ，有 $f[i][j]=\sum_{k=0}^nf[i-1][k]$ 。发现 $k$ 与状态无关，可以前缀和优化。

最后统计答案时枚举左边括号个数和左边左括号个数累加答案即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXL 2010

#define MAXN 100010

typedef unsigned long long ll;

#define MOD 1000000007

ll f[MAXL][MAXL];

ll s[MAXL][MAXL];

inline char getc()

{

	register char c = getchar();

	while(c != '(' && c != ')')c = getchar();

	return c;

}

char bra[MAXN];

int main()

{

	freopen("bracket.in","r",stdin);

	freopen("bracket.out","w",stdout);

	scanf("%d%d",&n,&m);

	if(n % 2 == 1)

	{

		puts("0");

		return 0;

	}

	deque<char> q;

	for(int i = 1;i <= m;++i)

	{

		if(getc() == '(')q.push_back('(');

		else

		{

			if(!q.empty() && q.back() == '(')q.pop_back();

			else q.push_back(')');

		}

	}

	int len = 0;

	int lef = 0,rig = 0;

	for(;;)

	{

		if(q.empty())break;

		if(q.front() == ')')++lef;

		else ++rig;

		bra[++len] = q.front();q.pop_front();

	}

	f[0][0] = 1;

	for(int i = 0;i <= n - m;++i)s[0][i] = 1;

	for(int i = 1;i <= n - m;++i)

	{

		f[i][0] = 1;

		s[i][0] = f[i][0];

		for(int j = 1;j <= i;++j)

		{

			f[i][j] = s[i - 1][j];

		}

		for(int j = 1;j <= n - m;++j)

		{

			s[i][j] = (s[i][j - 1] + f[i][j]) % MOD;

		}

	}

	ll ans = 0;

	for(int i = lef;i <= n - m;++i)

	{

		for(int j = (i + lef + 1) / 2;j <= i;++j)

		{

			ans = (ans + f[j][i - j] * f[(2 * j - 2 * i - lef + rig + n - m) / 2][(-2 * j + lef - rig + n - m) / 2] % MOD) % MOD;

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: DP-前缀和优化DP

wjh15101051