题解：AcWing 317 陨石的秘密

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing317. 陨石的秘密 - AcWing题库【题目描述】公元11380 1138011380年一颗巨大的陨石坠落在南极。于是灾难降临了地球上出现了一系列反常的现象。当人们焦急万分的时候一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察科学家们发现陨石上刻有若干行密文每一行都包含5 55个整数1 1 1 1 6 0 0 6 3 57 8 0 11 3 2845著名的科学家S S SSSS发现这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算他定义了一种S S SSSS表达式S S SSSS表达式是仅由{}[]()组成的字符串。一个空串是S S SSSS表达式。如果A AA是S S SSSS表达式且A AA中不含字符{}[]则( A ) (A)(A)是S S SSSS表达式。如果A AA是S S SSSS表达式且A AA中不含字符{}则[ A ] [A][A]是S S SSSS表达式。如果A AA是S S SSSS表达式则A {A}A是 SS 表达式。如果A AA和B BB都是S S SSSS表达式则 AB 也是S S SSSS表达式。例如()(())[] {()[()]} {{[[(())]]}}都是S S SSSS表达式。而()([])() [()不是S S SSSS表达式。一个S S SSSS表达式E EE的深度D ( E ) D(E)D(E)定义如下![[Pasted image 20260612085808.png]]例如(){()}[]的深度为2 22。密文中的复杂运算是这样进行的设密文中每行前4 44个数依次为L 1 L_1L1​L 2 L_2L2​L 3 L_3L3​D DD求出所有深度为D DD含有L 1 L_1L1​对{}L 2 L_2L2​对[]L 3 L_3L3​对()的S S SSSS串的个数并用这个数对当前的年份11380 1138011380求余数这个余数就是密文中每行的第5 55个数我们称之为神秘数。密文中某些行的第五个数已经模糊不清而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。【输入】共一行4 44个整数L 1 L_1L1​L 2 L_2L2​L 3 L_3L3​D DD。【输出】共一行包含一个整数即神秘数。【输入样例】1 1 1 2【输出样例】8【解题思路】![[Pasted image 20260612090241.png|825]]![[Pasted image 20260612090925.png|828]]![[Pasted image 20260612091230.png]]【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;// 定义模数常量constintmod11380;// 全局变量声明intL1,L2,L3,D;// L1, L2, L3: 三种括号的数量, D: 最大嵌套深度intf[35][15][15][15];// 动态规划数组f[d][i][j][k]表示深度不超过d时的方案数// 主函数入口intmain(){// 读取输入三种括号的数量和最大深度cinL1L2L3D;// 初始化边界条件没有括号时任何深度下都只有一种方案空串for(inti0;iD;i)f[i][0][0][0]1;// 动态规划按深度从小到大递推for(intd1;dD;d)for(inti0;iL1;i)// 第一种括号的数量for(intj0;jL2;j)// 第二种括号的数量for(intk0;kL3;k)// 第三种括号的数量{// 情况1最外层为第一种括号if(i0){// 枚举左边部分使用的括号数量for(intp0;pi;p)for(intq0;qj;q)for(intr0;rk;r)f[d][i][j][k](f[d][i][j][k]f[d-1][p][q][r]*f[d][i-p-1][j-q][k-r])%mod;}// 情况2最外层为第二种括号if(j0){// 左边不能有第一种括号枚举第二、三种括号的使用数量for(intq0;qj;q)for(intr0;rk;r)f[d][i][j][k](f[d][i][j][k]f[d-1][0][q][r]*f[d][i][j-q-1][k-r])%mod;}// 情况3最外层为第三种括号if(k0){// 左边不能有第一、二种括号枚举第三种括号的使用数量for(intr0;rk;r)f[d][i][j][k](f[d][i][j][k]f[d-1][0][0][r]*f[d][i][j][k-r-1])%mod;}}// 输出结果深度恰好为D的方案数 深度不超过D的方案数 - 深度不超过D-1的方案数if(D0)coutf[D][L1][L2][L3]%modendl;elsecout(f[D][L1][L2][L3]-f[D-1][L1][L2][L3]mod)%modendl;return0;}【运行结果】1 1 1 2 8