自动搬运

查看原文

来自洛谷，原作者为

	Tzs_yousa 南风知我意，吹梦到西洲。

搬运于2025-08-24 22:34:28，当前版本为作者最后更新于2021-11-13 09:12:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析题意

定义 $A$ 为 $B$ 的子序列当且仅当 $A$ 能由 $B$ 在顺序不改变的前提下删除若干元素后得到。

这句话是精髓，注意不是切开是删除，那是不是说我们统计有多少组匹配的括号，我们通过括号匹配求出来的匹配的括号的数量就是最多的可以匹配的，如果这么值大于我们要比较的 $m$ ， 那么肯定是可以满足的。

括号匹配（栈类型）

for (int i = 1; i <= n; i++)
		{
			if(s[i] == '(') 
			{
				st[++top] = i;//栈顶就是最新出现的左括号
			}
			else if(top)/与距离自己最近的那个括号匹配，匹配之后弹出栈就可以防止之后的影响
			{
				top--;
				ans++;
			}
		}

然后，随便放一下全套代码吧，虽然上面已经差不多了

#include<bits/stdc++.h>
#define int long long
const int MAXN = 1001;
using namespace std;
int t, n, m, len, s1, s2, ans, st[MAXN];
char s[MAXN];
signed main()
{
	ios::sync_with_stdio(false);
	cin >> t;
	while(t--)
	{
		int top = 0, ans = 0;
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
		{
			cin >> s[i];
		}
		for (int i = 1; i <= n; i++)
		{
			if(s[i] == '(') 
			{
				st[++top] = i;
			}
			else if(top)
			{
				top--;
				ans++;
			}
		}
		if(ans >= m)cout << 1 << endl;
		else cout << 0 << endl;
	}
	return 0;
}