CodeForces 1095-E

字 符 串 字符串 字符串	(	(	(	(	)	)
d p [ i ] dp[i] dp[i]	1	2	3	4	3	2
m [ i ] m[i] m[i]	1	2	2	2	2	2

字 符 串 字符串 字符串	(	(	）	(	)	)
d p [ i ] dp[i] dp[i]	1	2	1	2	1

字 符 串 字符串 字符串	）	）	）	(	（	)
d p [ i ] dp[i] dp[i]	-1	- 2	- 3	-2	-1
m [ i ] m[i] m[i]	-3	-3	-3	-2	-1

d p [ i ] = d p [ i − 1 ] + a [ i ] a [ i ] = { 1 s [ i ] = ( − 1 s [ i ] =    ) dp[i] = dp[i-1] + a[i] \quad a[i] = \begin{cases} 1 &\text {$s[i] = ($} \\ - 1 &\text {$s[i] = \;)$}\end{cases} dp[i]=dp[i−1]+a[i]a[i]={1−1​s[i]=(s[i]=)​

m [ i ] = m i n { m [ i ] , m [ i + 1 ] , ⋯   , m [ n − 1 ] } m[i] = min \lbrace m[i], m[i+1], \cdots, m[n-1] \rbrace m[i]=min{m[i],m[i+1],⋯,m[n−1]}

首先，我们可以知道，对于一个正确的括号匹配序列来说，

其 d p [ 0 ] = 1 , d p [ n − 1 ] = 0 , {dp[0] = 1, dp[n-1] = 0, } dp[0]=1,dp[n−1]=0, 并且最小值为0，假设其中有一个括号改变了，以 ) → ( 为 例 ， a [ i ] = − 1 → 1 , 那 么 d p [ n − 1 ] = 2 ) \to( 为例，a[i] = -1 \to 1, 那么dp[n-1] = 2 )→(为例，a[i]=−1→1,那么dp[n−1]=2 显而易见，当一个错误括号序列，当且仅当改变其中一个括号就可以将其变为正确括号序列时，其 d p [ n − 1 ] = 2 ( o r − 2 ) {dp[n-1] = 2 (or -2) } dp[n−1]=2(or−2)

对于一个错误序列，我们对其的第i个括号修改，其 d p [ i ] , d p [ i + 1 ] , … , d p [ n − 1 ] 全 都 − 2 a [ i ] ， dp[i], dp[i+1], \ldots, dp[n-1] 全都 -2a[i]， dp[i],dp[i+1],…,dp[n−1]全都−2a[i]，假设该操作正确，那么错误序列转化成正确序列，就要求 m [ i ] − 2 a [ i ] > = 0 { m[i] - 2a[i] >= 0 } m[i]−2a[i]>=0

详细代码如下：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e6+10;
int awsl[maxn];

int main() {
	int n;
	scanf("%d", &n);
	string s;
	cin >> s;
	vector<int> sum(n);
	vector<int> m(n);
	for (int i = 0; i < n; ++i) {
        if (s[i] == '(')    awsl[i] = 1;
        else    awsl[i] = -1;
	}
	sum[0] = awsl[0];
	for(int i = 1; i<n; ++i) {
		sum[i] = sum[i-1] + awsl[i];
	}
	m.back() = sum.back();
	for(int i = n - 2; i >= 0; i--) {
		m[i] = min(sum[i], m[i+1]);
	}
	int cnt = 0;
	for(int i = 0; i < n; ++i) {
		int v = 2*awsl[i];
		if(m[i] - v >= 0 && sum.back() - v == 0)    cnt++;
		if(sum[i] < 0) break;
	}
	cout << cnt << '\n';
}