送我退役的题，特此写一篇题解

分析

读题，发现给我一个现成的字符串我都不会快速判是否合法，跳了（真实案例）

读题，发现是求方案数、且较长区间的合法方案由较短区间的合法方案推来，所以是dp啊dp！

如果序列全是'?'，显然就是个裸的区间dp

如果有'('、'*'、')'呢？发现它们实质上比'?'少了两个贡献手段，所以对它们的处理可以自然地融入到dp中

于是我们设个状态\(dp_{l, r}\)表示塞爆\([l,r]\)的合法方案数

规则1、3显然很容易转化成式子

但是对规则2，直接做可能会使一个方案在多个断点被计算，所以加一维\(0/1\)表示方案最外层是否套括号

时间不够用？预处理

细节在dp时繁多的限制

代码

#include <bits/stdc++.h>

#define fast_cin ios::sync_with_stdio(false), cin.tie(nullptr)
#define ll long long

using namespace std;

const int N = 505;
const ll mod = 1e9 + 7;

int n, K;

char s[N];

bool allx[N][N];

ll dp[N][N][2];
ll qzh[N][N];
int reach[N];

inline bool isx(int x) { return s[x] == '*' || s[x] == '?'; }
inline bool isl(int x) { return s[x] == '(' || s[x] == '?'; }
inline bool isr(int x) { return s[x] == ')' || s[x] == '?'; }

inline ll cl(ll x) { return x >= mod? x - mod : (x < 0? x + mod : x); }



int main() {
    fast_cin;
    cin >> n >> K >> (s + 1);
    for(int l = 1; l <= n; ++l) {
	allx[l][l - 1] = 1;
	for(int r = l; r <= n; ++r) {
	    if(isx(r)) allx[l][r] = 1;
	    else break;
	}
    }
    for(int len = 2; len <= min(n, K + 2); ++len) {
	for(int l = 1; l <= n - len + 1; ++l) {
	    int r = l + len - 1;
	    if(isl(l) && isr(r) && allx[l + 1][r - 1]) {
		++dp[l][r][0], ++dp[l][r][1];
	    }
	}
    }
    for(int r = 1; r <= n; ++r) {
	for(int i = r; i >= 1; --i) {
	    qzh[i][r] = cl(qzh[i + 1][r] + dp[i][r][1]);
	}
    }
    for(int i = 1; i <= n; ++i) {
	for(int j = i + 1; j <= min(i + K + 1, n); ++j) {
	    if(allx[i + 1][j - 1]) reach[i] = j;
	    else break;
	}
    }
    for(int len = 4; len <= n; ++len) {
	for(int l = 1; l <= n - len + 1; ++l) {
	    int r = l + len - 1;
	    if(!isl(l) || !isr(r)) {
		qzh[l][r] = cl(qzh[l + 1][r] + dp[l][r][1]); // Death
		continue;
	    }
	    dp[l][r][0] = cl(dp[l][r][0] + dp[l + 1][r - 1][1]);
	    dp[l][r][1] = cl(dp[l][r][1] + dp[l + 1][r - 1][1]);
	    for(int k = 1; k <= min(K, r - l - 2); ++k) {
		if(allx[r - k][r - 1]) {
		    dp[l][r][0] = cl(dp[l][r][0] + dp[l + 1][r - 1 - k][1]);
		    dp[l][r][1] = cl(dp[l][r][1] + dp[l + 1][r - 1 - k][1]);
		}
		if(allx[l + 1][l + k]) {
		    dp[l][r][0] = cl(dp[l][r][0] + dp[l + 1 + k][r - 1][1]);
		    dp[l][r][1] = cl(dp[l][r][1] + dp[l + 1 + k][r - 1][1]);
		}
	    }
	    for(int i = l; i <= r - 1; ++i) {
		int j = min(reach[i], r);
		dp[l][r][1] = cl(dp[l][r][1] + dp[l][i][0] * cl(qzh[i + 1][r] - qzh[j + 1][r]) % mod);
	    }
	    qzh[l][r] = cl(qzh[l + 1][r] + dp[l][r][1]);
	}
    }
    cout << dp[1][n][1] << "\n";
    return 0;
}