一道有点巧妙的DP，一篇有点清晰的方法
大意就是给了一个长度为n的括号串S，要求在S之前加一个串P，在S之后加一个串Q，使得总长为m且保证PSQ合法的方案数。 我们一共需要添加n-m的括号，我们定义括号串的值为左括号-右括号的个数 设DP状态f[i][j][0/1]： f[i][j][0]表示添加的前i个括号中，括号串的值为j，且没有拼接上S的方案数，例如xxxxx(当前位置) f[i][j][1]表示添加的前i个括号中，括号串的值为j，拼接上S之后的方案数,例如xxxxSxxxx(当前位置)
f[i][j][0]+=f[i-1][j+1][0]+(j-1>=0?f[i]-1[j-1][0]:0) f[i][j][1]+=f[i-1][j+1][1]+(j-1>=0?f[i]-1[j-1][1]:0) 这两个状态分别对应加上(和) 然后对于加上S使得第三维从0->1的转化我们要在上述转移全部转移了之后做，下面思考要满足什么条件： 设S的值为val,S的前缀中右括号比左括号多的值的最大值为pre_mn，显然有拼接S的时候前面P至少有pre_mn个左括号：
if(j-val>=pre_mn) f[i][j][1] += f[i][j-val][0];
然后就写完了；
完整Code: https://codeforces.com/contest/629/submission/178593539
上一篇：
通过多线程提高代码的执行效率例子
下一篇：
VS2022·初尝试评测（非专业测评）