口腔网站模板,网站开发环境有哪些php,更新电脑版wordpress,怀化电视台网站本篇鸡汤#xff1a;没有人能替你承受痛苦#xff0c;也没有人能拿走你的坚强. 欢迎拜访#xff1a;羑悻的小杀马特.-CSDN博客 本篇主题#xff1a;带你解答洛谷的括号序列问题#xff08;绝对巧解#xff09; 制作日期#xff1a;2025.01.10 隶属专栏#xff1a;C/C题… 本篇鸡汤没有人能替你承受痛苦也没有人能拿走你的坚强. 欢迎拜访羑悻的小杀马特.-CSDN博客 本篇主题带你解答洛谷的括号序列问题绝对巧解 制作日期2025.01.10 隶属专栏C/C题海汇总 目录
本篇简介
一·题目介绍
二·思路叙述
2.1判断独立性
2.2空隙法及填充gap表
2.3填充dp表
2.3.1dp状态方程规定:
2.3.2dp的状态转移方程推导及填充
2.4·镜像法
2.5细节处理
三·代码汇总
四.个人小结 本篇简介
本篇主体还是动态规划之前篇介绍了对它的讲解概念因此本篇就不做多解释下面就是利用动态规划结合概率论推导独立性公式两步走并采用镜像法优化一下最后动态规划得到答案后采用独立性求积方法得出答案。
一·题目介绍 洛谷链接 [蓝桥杯 2021 省 AB] 括号序列 - 洛谷
测试用例 输入((() 输出5 二·思路叙述
当我们看到了括号填充类似问题是不是想到了leetcode的有道括号生成问题看着好像 链接LCR 085. 括号生成 - 力扣LeetCode
下面我们展示下leetcode的代码 //思路对于返回的字符串组合可以考虑是否是决策树的叶子然后用决策树dfs:即根据n也就是判断递归条件剪枝左右支为()它们的选择
//然后画出决策树分析递归条件完成dfs设计class Solution {
public://全局变量的设计int left0;int right0;string path;vectorstring ret;vectorstring generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){//递归出口if(path.size()2*n){ret.emplace_back(path);return;}//判断进入递归的条件剪枝逆向if(leftn){path(;left;dfs(n);path.pop_back();left--;//回溯}if(rightleft){path);right;dfs(n);path.pop_back();right--;//回溯}}
};
但是我们仔细一下看本题并不是自己生成所有种类的正确情况而是让我们自己在它给例子去填充让它有效。 看到这里根据我们上一篇的经验就很容易想到动态规划去解答因此leetcode上面深度优先遍历的方法就寄掉了。
因此下面我们就用动态规划思想去解答但是它也是不好想到甚至我们去看题解是不是都看不懂比如 这里可以看出要么就是三层for嵌套循环填dp以及很多人会发现题解甚至都看不懂即便看懂还要琢磨很久才会明白当然这里博主也是因此博主在这出一篇文章来解释一下让大家可以更加明白这道题是如何解答的。
那么下面我们就以题目给的例子来畅谈
2.1判断独立性 首先我们的任务就是要么填充右括号来干掉左括号要么填充左括号来干掉右括号反正就是要得到这样以最小的添加括号让它合法的添加方法数那么下面我们说一下结论 这里可以知道添加右括号使它合法也就是利用右括号干掉左括号的方法数和添加左括号方法数是独立的----而题目要求是添加左括号和右括号是都行的,因此最后就可以转化成添加左括号方案数与右括号方案数之积两者是独立的 。 证明
这里为什么可以得到上面说的结论直接就把问题简单化单一化了
这里需要用到的概率论的公式
说白了就是A B两个事件如果互不干扰互不影响那么此时两种同时发生的概率就是两者单独发生概率之积 而本题呢
我们给它的目的简化一下使得它更贴近这题目其实就是要求让我们要么补充左括号要么补充右括号对应把相反括号干掉也就是所说的使得左右括号都合法而我们补充右括号使得左括号合法并没有影响其他右括号的合法性因为我们没有补充左括号--所以左右括号的合法性是独立的。
因此我们可以拆开来分别求它们单独的合法性种类然后求个积就是题目要的使得例子左右括号都合法的种类数。 这里注意下:题目所说最少填充括号的意思就是比如对于((()我们不能无缘无故让添加一对括号让它合法((()()()()))类似这样。
因此我们可以得到一个公式 ret(re_left*re_right)%1e97 这里题目要求结果太大要取模 解释一下也就是我们使左括号合法的种类*使右括号合法的种类。
那么也就是我们怎么求左括号和发的种类这里我们引入一下空隙法后面我们得知独立性后就基于判断左括号合法性来讲解。
2.2空隙法及填充gap表
这里我们以左括号为例就是我们每当多一个左括号就相当于多了一个可以填充右括号的空隙但是当我们遍历到右括号空隙个数可以理解成没变但遍历到当前0~当前空隙能填充右括号个数要少一个保证非负性大于0才减少
然后就是我们搞一个空隙数组记录的就是前i个空隙中最多可以放多少个括号gap[i]这里为了方便我们一一对应因此下标从1开始对应的是前多少个空隙
下面我们举个例子吧
比如((() :这里有三个空隙具体变化gap数组的值随着遍历:1--2--3--2这注意是吧第三个空隙的最大容量减1。
再比如 因为多少个左括号就意味着可以补充多少右括号但是空隙最大容量也就是补充括号的个数是随着与之反作用的括号相关的
因此下面重点我们总结一下空隙规则这里我们都以补充右括号使左括号合法来谈 ①空隙的个数也就是左括号的个数 ②当遇到右括号的话空隙所容纳的括号数就减少前提是大于0。 下面就根据上述所讲填充空隙表gap
l:记录的左括号个数也就是空隙个数
void init_gap() {//填充gap数组也就是判断多少个空隙以及前多少个空隙的
//最大容量for (int i 0; i N; i) {if (s[i] () {l;gap[l] gap[l - 1] 1;}else gap[l] 0 ? gap[l]-- : 1;//这里注意当干右括号的时候//因为是求得最少补充的左括号数故不能出现负}
}
但是这里我们就可以得到公式也就是判断填右括号使得左括号合法的规定 我们gap数组存的都是遍历到当前空隙开始从0~i补充右括号最大个数因此我们当填充dp表的时候遍历填写括号个数的要加一个判断 填充括号个数gap[遍历到当前的空隙] 即 igap[j]。 那又要问了为什么动态规划不是填充dp表为啥搞个空隙表因为后面我们会填充dp就是根据多少个空隙遍历到哪里最多可以填充多少个括号来填充的故肯定是有用的。
2.3填充dp表
2.3.1dp状态方程规定:
那么首先我们肯定要先定义dp表的状态
因为它是遍历到哪里然后又要在这段区间填充括号多少个使它变得合法因此最好搞一个二维dp表。
那么我们结合上面搞的空隙表规定状态
dp[i][j]代表遍历到第j个空隙处可以在0~i个空隙内可以填充i个括号的种类数这里我们遍历只按照左括号走
2.3.2dp的状态转移方程推导及填充
这里由于让下标与实际意义对应及可能会出现状态方程自己初始化需要前边的值我们选择多开并手动初始化。
首先呢对于大多数人直接用脑子按照这个逻辑去想状态方程是啥样肯定是困难的因此我们搞一个简单的例子带大家总结一下状态转移方程 首先我们根据这个例子自己按照dp状态规定填好dp表但是为什么第一行都填0呢
这就是我们状态方程自己循环填充要用到的需要我们提前进行初始化
也就是把0个括号插入到0-l个空隙插入的方案:这里我们可以理解成把0个即插入“空气”这种插法故只有一种情况虽然有些勉强其次就是我们只能根据找规律细心的话如果我们第一行不填写可以发现如果都填写1的话可以得到一个公式 其实就是我们那个填写dp表的一个“1”形状dp值之和我们可以根据这个公式来往上递推成“/”形状的dp值这样就无需再来一层for循环就像上面说的o(N^3一样复杂度的三层for了只需取前面填充的两个dp值就好了。
如 因此公式化简也就是我们填充dp表要用的公式 当然了后面我们写的时候要对1e97取模题目说明就不用说了吧还有就是long long的奇妙之处了
那dp填表的过程这个公式就ok吗
当然还会有条件限制这里我们在填充空隙表gap数组的时候就说了 加上这个条件后填充dp就ok了。
这个条件就解释了为什么最后填充三个括号为0以及这么多位置填写0的原因了。
最后我们要的是在0~j个空隙能填充的最大括号数的方案数遍历到对应空隙此空隙里面放的gap数组值即
dp[gap[l]][l];
这样我们就得到了上面所说的re_left值了记住也是long long 。
后面我们在去求re_right难道也是写一个类似的两个函数去完成吗
当然不用了直接给他镜像一下就等同于判断左括号的合法性了这也就是本篇标题提到的镜像法的巧妙了。
2.4·镜像法
这里虽然名字起的多好高级其实并不难理解之所以这么操作就是为了让我们不用再多写函数就可以完成对右括号像左括号一样类似的检验所以为什么起这个名字呢下面看张图片 这样就可以看出了我们要检查右括号的合法性补充左括号其实就是把它镜像一下然后再检验一次左括号的合法性就行了。
其实也不难操作就是遍历一下原串把左括号改成右括号右括号改成左括号然后再利用迭代器逆置一下就好
最后我们根据独立性返回两者之积就好了但是注意范围long long ,其次就是取模。
2.5细节处理
也就是分享一下博主在写这道题遇到的困难即一些细节问题没注意到而导致的
比如
①博主写的代码这里大都用的全局变量好处就是可以让函数不用传参坏处就是如果再次使用就要重新初始化 l0;//再次填充gap是需要对它初始化0memset(dp,0,sizeof(dp));//再次用填充dp表也要对它初始化0 ②就是结果要是long long类型否则即不能通过比如和dp值有关都要是long long最后答案等否则就这样 这就是re_left和re_right没有long long的结果果真映射那句话“不加long long 见祖宗” 。 ③其次就是那些细节问题比如填充gap表注意 填充dp表要注意 这样细节都处理好就大差不大了。
三·代码汇总
#includebits/stdc.h
using namespace std;
using ll long long;
#define MAX 1000000007
#define C 5000
ll dp[C1][C 1] { 0 };//表示把i个括号插入到前j个空隙的方案数
int gap[C 1] { 0 };//下标是第几个空隙值是空隙的最大左括号容量
string s;
int N;
int l0;//记录左括号数量
void init_gap() {//填充gap数组也就是判断多少个空隙以及前多少个空隙的
//最大容量for (int i 0; i N; i) {if (s[i] () {l;gap[l] gap[l - 1] 1;}else gap[l] 0 ? gap[l]-- : 1;//这里注意当干右括号的时候//因为是求得最少补充的左括号数故不能出现负}
}
ll get_ans() {for (int i 0; i l; i) dp[0][i] 1;for (int i 1; i l; i) {for (int j 1; j l; j) dp[i][j] gap[j] i ? (dp[i - 1][j] dp[i][j - 1]) % MAX:0;//填充的括号数量不能超过前多少个空隙所能容下的最大 }return dp[gap[l]][l];//输出的是把最大空隙数所能容的括号数填入的最多方式数
}
void mapping_r_to_l(){//补充左括号干掉右括号转化成补充右括号干掉左
//镜像一下子,使得写的干左括号的函数还可以用reverse(s.begin(), s.end());for (int i 0; i N; i)s[i] (s[i] ( ? ) : ();
}
int main() {cin s;N s.size();init_gap();ll re_left get_ans();mapping_r_to_l();l0;//全局劣势init_gap();memset(dp,0,sizeof(dp));//全局劣势ll re_right get_ans();cout (re_left * re_right) % MAX endl;//利用独立性return 0;}
最后也是满分AC了 四.个人小结 这里对于动态规划的题型做法就不总结了因为上篇总结过啦具体可看【动态规划篇】步步带你深入解答成功AC最优包含问题通俗易懂版-CSDN博客 此外就是对于不熟悉的题目我们要对看看题解看看大佬们是用什么奇妙的方法解答的当然可能会看不懂但是我们不要放弃一天看不懂就多看几天只要愿意学习别人的解法总是会可以悟懂的这里说一下博主写这篇文章其实也是学习了大佬的写法当然也是看了好几天所以我们自己不熟练就要多多学习必然的解法做好总结尽最大可能去吸收它。这里博主建议如果看题解看不懂尽量找写的比较详细的博客去学习博主自荐一下可以参考向博主这样写的文章去看去学习如有不足指出来博主会尽力修改 还是那句话只要愿意学肯定能学会的关键还是在于你的抉择。 对此我之所以能写出这篇文章还要感谢一位博主写的它的文章通过阅读揣摩那位博主的文章加上自己的理解才可创作出这篇文章相当于对那位博主的文章的深刻解释以及加上了自己的理解吧
借鉴的博主文章链接第十二届蓝桥杯B组省赛括号序列题解_蓝桥杯判断括号合法-CSDN博客 当然还是先建议把博主的文章读懂再去读这位博主的文章毕竟个人认为自己的文章对它解释了很多地方更方便读者阅读。 感谢大家阅读
