P7248 [BalticOI 2012] 括号 (Day1)

题目传送门

题目思路

简单 dp 题。

设 $dp_{i,j}$ 表示到第 $i$ 个位置有 $j$ 个未匹配括号时的方案数，则易推出状态转移方程。

• 当当前遍历到的字符不是左括号：$dp_{i,j} = dp_{i-1,j+1}$。
• 当当前遍历到的字符是左括号：$dp_{i,j} = dp_{i-1,j+1} + dp_{i-1,j-1}$。

记得取余 $10^9 + 9$！

由于数据范围大，所以要使用滚动数组优化，防 MLE。

此外，吸氧也要卡常！

code

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 9;
int dp[2][30005];
signed main()
{
	dp[0][0] = 1;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		char a;
		cin >> a;
		for (int j = 0; j <= min(n - i, i); j++)
		{
			if (a == ')' || j == 0)
				dp[i & 1][j] = dp[i + 1 & 1][j + 1] % mod;
			else
				dp[i & 1][j] = (dp[i + 1 & 1][j + 1] + dp[i + 1 & 1][j - 1]) % mod;
		}
	}
	cout << dp[n & 1][0];
	return 0;
}