本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing4919. 括号 - AcWing题库【题目描述】正则括号序列定义如下空序列是正则括号序列。如果s ss是正则括号序列则( s ) (s)(s)和[ s ] [s][s]是正则括号序列并且如果a aa和b bb均为正则括号序列则a b abab也是正则括号序列。没有其它序列是正则括号序列。例如以下序列均是正则括号序列()[](())()[]()[()]而以下序列均不是正则括号序列(])(([)]([(]。给定一个长度为n nn的括号序列a 1 a 2 … a n a_1a_2…a_na1​a2​…an​请你找到该序列的最长正则括号子序列的长度。即找到最大的m mm使得对于索引i 1 , i 2 , … , i m i_1,i_2,…,i_mi1​,i2​,…,im​1 ≤ i 1 i 2 … i m ≤ n 1≤i_1i_2…i_m≤n1≤i1​i2​…im​≤n满足a i 1 a i 2 … a i m a_{i_1}a_{i_2}…a_{i_m}ai1​​ai2​​…aim​​是正则括号序列。例如如果给定括号序列为([([]])]则最长正则括号子序列为[([])]。【输入】输入包含多组测试数据。每个数据占一行包含一个由(、)、[、]构成的字符串表示给定括号序列。最后包含一行end表示输入结束。【输出】每组数据输出一行结果一个整数表示最长正则括号子序列的长度。【输入样例】((())) ()()() ([]]) )[)( ([][][) end【输出样例】6 6 4 0 6【算法标签】#区间DP【代码详解】#includebits/stdc.husingnamespacestd;constintN105;string str;// 输入的括号序列intf[N][N];// 动态规划数组f[i][j]表示区间[i,j]的最长合法括号子序列长度intmain(){while(cinstr)// 读入字符串{if(strend)// 如果是结束标志break;intnstr.length();// 字符串长度str str;// 在字符串前加一个空格使下标从1开始memset(f,0,sizeof(f));// 初始化dp数组为0for(intlen2;lenn;len)// 枚举区间长度{for(inti1;ilen-1n;i)// 枚举区间起点{intjilen-1;// 区间终点// 如果两端括号匹配if(str[i](str[j])||(str[i][str[j]]))f[i][j]max(f[i][j],f[i1][j-1]2);// 更新最长长度for(intki;kj-1;k)// 枚举分割点f[i][j]max(f[i][j],f[i][k]f[k1][j]);// 合并左右区间}}coutf[1][n]endl;// 输出整个序列的最长合法括号子序列长度}return0;}【运行结果】((())) 6 ()()() 6 ([]]) 4 )[)( 0 ([][][) 6 end