括号匹配序列题小总结

他们说这是一个经典的栈的匹配问题，读入括号，如果栈顶遇到匹配的就取出栈顶，为了防止栈空导致RE，我们先存个挡枪的小东西。系列读完后如果栈顶不是那个挡枪的，说明序列不合法。

另外如果出现以下情况，肯定也不合法：）（、] ] 、( ] 、）] 、[ ) 、] )

传送门：UVA673 平衡的括号 Parentheses Balance - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#define maxn 101000
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

void Stack(string str)
{
	stack s;
	s.push('*');
	int len=str.length();
	bool flag=true;
	for(int i=0;i>t;
    while(t--)
	{
		string s;
    	cin>>s;
   		Stack(s);
	}
}

然后改一下输出，可以做另一个入门：P1739 表达式括号匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

另外，关于栈，还有一个简单题：P4387 【深基15.习9】验证栈序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#define maxn 101000
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

void Stack()
{
	int n,a[maxn],b[maxn];
	cin>>n;
	stack s;
	for(int i=0;i>a[i];
	for(int i=0;i>b[i];
	int tot=0; 
	for(int i=0;i>t;
    while(t--)
	{
		
   		Stack();
	}
}

传送门：P1944 最长括号匹配 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

看博客看到的：最值问题可以用贪心、dp、二分等等。

记dp[i]为以s[i]为结尾的最长括号匹配。

转移方程的由来，dp[i-1]是以s[i-1]s[i−1]结尾的最长括号匹配，详情可以看图。

 代码：

#include 
const int maxn=1e6+5;
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int dp[maxn];
void Stack()
{
	char s[maxn];
	cin>>s+1;
	int ans=0,index=0;//ans记录最长括号匹配的长度，index记录最长括号匹配的结尾坐标 
	int n=strlen(s+1);
	for(int i=2;i<=n;i++)
	{
		if( (s[i]==')'&&s[i-1-dp[i-1]]=='(') || (s[i]==']'&&s[i-dp[i-1]-1]=='['))
			dp[i]=dp[i-1]+2+dp[i-2-dp[i-1]];
		else
			dp[i]=0;
		if(dp[i]>ans)
			ans=dp[i],index=i;		
	}
	for(int i=index-ans+1;i<=index;i++)
		cout< 
三、记忆化搜索 
记忆化搜索=搜索+动态规划
 
记忆化搜索的思想：在搜索的过程中，记录一些状态的答案，减少重复搜索（并非减少重复生成），典型应用场景是经过不同的路径转移到相同的状态的dfs问题。也是对递归进行剪枝。
 
四、CF149D Coloring Brackets
 
传送门：Problem - 149D - Codeforces
 
题目给出的是合法序列，所以匹配到的边不会相交，可以用许多分割线分割为不同长度的合法子序列，比如：（（））（）（（（）（））。即不能匹配的两端就放在两个区间里。
 
一道区间dp，可以想到用dp【l】【r】表示区间【l，r】内合法的方案数，但是还要满足相邻位置的颜色不同，所以要考虑左右的颜色。
 
所以最后我们用dp[l,r,x,y]为区间[l,r]，左端点颜色为x，右端点颜色为y的合法方案数。
 
不用担心，因为是从小序列转移过来的，所以内层是满足的，我们只用考虑外面挨着的括号就行。
 
颜色：0为不涂色，1为红色，2为蓝色。
 
 
1.关于初始化（对于最小的序列（）来说，方案只有一）
 
当left+1=right时，说明刚好是（），初始化：dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
 
2.普通的left和right匹配，即（......），根据最外面的括号颜色不同有不同的转移，看图。
 
dp[i][j][][]dp[i][j][][] 是由 dp[i+1][j−1][][]dp[i+1][j−1][][] 转移而来,并且color i≠color i+1 且 color j≠color j−1。
 
递归处理[l+1,r-1]
 
 
 3.如果left和right不匹配，说明要分割成两个块：【l,match(l)】和【match(l)+1,r】，因为k=match(l)与k+1相邻，所以二者不同色。
 
for(int i=0;i<=2;i++) //第一个括号的颜色
 
for(int j=0;j<=2;j++) //match[l]的颜色
 
for(int p=0;p<=2;p++) //match[l]+1的颜色
 
for(int q=0;q<=2;q++) //r的颜色
 
{
 
        if((j==1&&p==1)||(j==2&&p==2)) //j与k相邻，颜色要不同
 
                continue;
 
        dp[l][r][i][q]=(dp[l][r][i][q]+dp[l][match[l]][i][j]*dp[match[l]+1][r][p][q]%mod)%mod;
 
}
 
4.关于记忆化搜索：
 
解题过程是先解析分割出最优的子问题然后确定dp的含义，方式是递归。所有操作都在原有的合法序列上增删一对括号或者分割合法序列为子序列或者合并子合法序列。
 
5.代码：
 
#include 
const int maxn=777;
const int mod=1e9+7;
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll dp[maxn][maxn][3][3],match[maxn];
ll n;
void Stack()//寻找匹配的两个边边坐标，牵根线~ 
{
	string s;
	cin>>s;
	stack st;
	n=s.length();
	for(int i=0;i