P7914 [CSP-S 2021] 括号序列 题解

由于众所周知,题意略.

容易发现两维dp必死无疑.考虑将不同类型分开:

• 星
• 括号
• 括号星
• 星括号
• 括号星括号,括号括号,括号
• 星括号星,星

共六种.转移见代码.

#include
#include
using namespace std;
const int N=505;
const int MOD=1000000007;
int n,k;
long long dp[N][N][7];
string a;
/*
1: *************
2: ********(...)
3: (...)********
4: (...)***(...)
5: (...........)
6: ****(...)****
*/
int main() {
	freopen("bracket.in","r",stdin);
	ios::sync_with_stdio(false);
	cin>>n>>k;
	cin>>a;
	a=' '+a;
	for (int i=1; i<=n; i++)
		dp[i][i-1][1]=1;//方便下面边界情况转移,即len较短减越位的情况. 
	for (int len=1; len<=n; len++) {
		for (int s=1; s<=n-len+1; s++) {
			int e=s+len-1;
			if (len<=k&&(a[e]=='?'||a[e]=='*'))
				dp[s][e][1]=dp[s][e-1][1];
			if ((a[s]=='('||a[s]=='?')&&(a[e]==')'||a[e]=='?'))
				dp[s][e][5]=(dp[s+1][e-1][1]+dp[s+1][e-1][2]+dp[s+1][e-1][3]+dp[s+1][e-1][4])%MOD;
			//括号=(星+星括号+括号星+括号星括号+括号),括号匹配.
			for (int k=s; k