题解 | #括号匹配深度#

区间dp，栈

我们开一个数组表示和第个位置配对的位置，即是一个配对的括号，同时把这些配对的二元组加进中，之后按照从小到大排序，即我们先处理长度为2的括号，接着长度为4，6等等。

我们同时开一个表示区间的深度，对于长度为2的区间，我们直接让，对于区间长度大于的区间，我们枚举中间的合法区间分界处，令，那么;

注意初始化就行。时间复杂度也是很小的。

#include<bits/stdc++.h>
#include <vector>
using namespace std;

int main() {
	string s;
	cin >> s;
	int n=s.size();
	s=" "+s;
	stack<int> stk;
	vector<int> match(n+1);
	vector<array<int,2>> seg;
	for(int i=1;i<=n;i++){
		if(s[i]=='('){
			stk.push(i);
		}else{
			int v=stk.top();
			match[i]=v;
			match[v]=i;
			seg.push_back({v,i});
			stk.pop();
		}
	}
	int ans=1;
	sort(seg.begin(),seg.end(),[&](array<int,2> x,array<int,2>y){
		return x[1]-x[0]<y[1]-y[0];
	});
	vector<vector<int>> dp(n+1,vector<int>(n+1,0));
	for(auto[l,r]:seg){
		if(r-l+1==2){
			dp[l][r]=1;
			continue;
		}
		int cnt=0;
		for(int k=l+1;k<r;k++){
			int mn=min(match[k],k),mx=max(k,match[k]);
			cnt=max(cnt,max(dp[mn][mx],dp[mx+1][r-1]));
		}
		dp[l][r]=cnt+1;
		ans=max(ans,cnt+1);
	}
	cout << ans << endl;
}
// 64 位输出请用 printf("%lld")