桂林网站定制建设,vue本地访问服务器跨域,如何做网站运营呢,全国企业信息官网网站题目链接
[CSP-S 2021] 括号序列
题目描述
小 w 在赛场上遇到了这样一个题#xff1a;一个长度为 n n n 且符合规范的括号序列#xff0c;其有些位置已经确定了#xff0c;有些位置尚未确定#xff0c;求这样的括号序列一共有多少个。
身经百战的小 w 当然一眼就秒了这…题目链接
[CSP-S 2021] 括号序列
题目描述
小 w 在赛场上遇到了这样一个题一个长度为 n n n 且符合规范的括号序列其有些位置已经确定了有些位置尚未确定求这样的括号序列一共有多少个。
身经百战的小 w 当然一眼就秒了这题不仅如此他还觉得一场正式比赛出这么简单的模板题也太小儿科了于是他把这题进行了加强之后顺手扔给了小 c。
具体而言小 w 定义“超级括号序列”是由字符 (、)、* 组成的字符串并且对于某个给定的常数 k k k给出了“符合规范的超级括号序列”的定义如下
()、(S) 均是符合规范的超级括号序列其中 S 表示任意一个仅由不超过 k \bm{k} k 个字符 * 组成的非空字符串以下两条规则中的 S 均为此含义如果字符串 A 和 B 均为符合规范的超级括号序列那么字符串 AB、ASB 均为符合规范的超级括号序列其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串如果字符串 A 为符合规范的超级括号序列那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。所有符合规范的超级括号序列均可通过上述 3 条规则得到。
例如若 k 3 k 3 k3则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列但字符串 *()、(*()*)、((**))*)、(****(*)) 均不是。特别地空字符串也不被视为符合规范的超级括号序列。
现在给出一个长度为 n n n 的超级括号序列其中有一些位置的字符已经确定另外一些位置的字符尚未确定用 ? 表示。小 w 希望能计算出有多少种将所有尚未确定的字符一一确定的方法使得得到的字符串是一个符合规范的超级括号序列
可怜的小 c 并不会做这道题于是只好请求你来帮忙。
输入格式
第一行两个正整数 n , k n, k n,k。
第二行一个长度为 n n n 且仅由 (、)、*、? 构成的字符串 S S S。
输出格式
输出一个非负整数表示答案对 10 9 7 {10}^9 7 1097 取模的结果。
样例 #1
样例输入 #1
7 3
(*??*??样例输出 #1
5样例 #2
样例输入 #2
10 2
???(*??(?)样例输出 #2
19提示
【样例解释 #1】
如下几种方案是符合规范的
(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)【数据范围】
测试点编号 n ≤ n \le n≤特殊性质 1 ∼ 3 1 \sim 3 1∼3 15 15 15无 4 ∼ 8 4 \sim 8 4∼8 40 40 40无 9 ∼ 13 9 \sim 13 9∼13 100 100 100无 14 ∼ 15 14 \sim 15 14∼15 500 500 500 S S S 串中仅含有字符 ? 16 ∼ 20 16 \sim 20 16∼20 500 500 500无
对于 100 % 100 \% 100% 的数据 1 ≤ k ≤ n ≤ 500 1 \le k \le n \le 500 1≤k≤n≤500。
算法思想
根据题目描述符合规范的超级括号序列有下面几种情况
()(S)将S加上一层括号是符合规范的。其中 S 表示任意一个仅由不超过 k \bm{k} k 个字符 * 组成的非空字符串(A)表示对一个符合规范的序列再加一层括号也符合规范的(SA)、(AS)表示在一个符合规范的序列左边或右边连接一个S再加一层括号也是符合规范的AB表示并排在一起的符合规范的序列也是合法的ASB表示将S放在并排在一起的符合规范的序列之中也是合法的
若 k 3 k 3 k3则字符串 ((**()*(*))*)(***)是否合法可以这样分析
字符串的右边(***)是一个合法的序列(S)如果左边的子串((**()*(*))*)是一个合法序列则并排在一起符合规范AB。((**()*(*))*)如果其中的子串(**()*(*))是一个合法序列则符合规范(AS)。(**()*(*))如果其中的子串()*(*)是一个合法序列则符合规范(SA)。()*(*)符合规范ASB是一个合法序列
因此整个序列是符合规范的超级括号序列。
也就是说对于字符串中任意一个区间 [ i , j ] [i,j] [i,j]判断是否符合规范则需要判断其子区间是否符合规范那么可以使用区间动态规划来处理。
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示将字符串中从 i i i到 j j j位置的字符确定后得到的字符串是一个符合规范的超级括号序列的方案数。由于从 i i i到 j j j位置的字符可能是其中的一个子串因此存在多种合法的状态 f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]表示由单独的符合规范的超级括号序列组成的方案数形式如()、(S)、(A)、(SA)、(AS)。 f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]表示由并排的符合规范的超级括号序列组成的方案数形式如AB、ASB。 f [ i ] [ j ] [ 2 ] f[i][j][2] f[i][j][2]表示仅由不超过 k \bm{k} k 个字符 * 组成的方案数形式如*、**…。需要注意的是只有 * 组成的子串无法单独构成符合规范的超级括号序列。 f [ i ] [ j ] [ 3 ] f[i][j][3] f[i][j][3]表示由符合规范的超级括号序列不超过 k \bm{k} k 个* 组成的方案数形式如AS。该方案也无法单独构成符合规范的超级括号序列。 f [ i ] [ j ] [ 4 ] f[i][j][4] f[i][j][4]表示由不超过 k \bm{k} k 个 * 符合规范的超级括号序列组成的方案数形式如SA。该方案也无法单独构成符合规范的超级括号序列。
最终的方案总数为 f [ 1 ] [ n ] [ 0 ] f [ 1 ] [ n ] [ 1 ] f[1][n][0]f[1][n][1] f[1][n][0]f[1][n][1], 其中 n n n表示字符串 S S S的长度。
状态计算 f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]表示由单独的符合规范的超级括号序列组成的方案数那么去掉 i i i、 j j j位置的括号后子串的形式可以是空串、A、AB、S、SA、AS的任意一种情况因此 f [ i ] [ j ] [ 0 ] f [ i 1 ] [ j − 1 ] [ 0 ] f [ i 1 ] [ j − 1 ] [ 1 ] f [ i 1 ] [ j − 1 ] [ 2 ] f [ i 1 ] [ j − 1 ] [ 3 ] f [ i 1 ] [ j − 1 ] [ 4 ] f[i][j][0]f[i1][j-1][0]f[i1][j-1][1]f[i1][j-1][2]f[i1][j-1][3]f[i1][j-1][4] f[i][j][0]f[i1][j−1][0]f[i1][j−1][1]f[i1][j−1][2]f[i1][j−1][3]f[i1][j−1][4] 注意当长度为 2 2 2时也就是只有括号的情况下子串为空 f [ i ] [ j ] [ 0 ] 1 f[i][j][0] 1 f[i][j][0]1。 f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]表示由并排的符合规范的超级括号序列组成的方案数如果以一个符合规范的超级括号序列B进行分类那么子串的形式可以是A、AS。因此可以枚举最后一个B和前面的分界点 k k k f [ i ] [ j ] [ 1 ] ∑ k i j − 1 ( f [ i ] [ k ] [ 0 ] f [ i ] [ k ] [ 1 ] f [ i ] [ k ] [ 3 ] ) × f [ k 1 ] [ j ] [ 0 ] f[i][j][1]\sum_{ki}^{j-1}(f[i][k][0]f[i][k][1]f[i][k][3])\times f[k1][j][0] f[i][j][1]∑kij−1(f[i][k][0]f[i][k][1]f[i][k][3])×f[k1][j][0] f [ i ] [ j ] [ 2 ] f[i][j][2] f[i][j][2]表示仅由 * 组成的方案数只能从状态 [ 2 ] [2] [2]转移过来所以 f [ i ] [ j ] [ 2 ] f [ i 1 ] [ j ] [ 2 ] f[i][j][2]f[i1][j][2] f[i][j][2]f[i1][j][2] 注意当长度为 1 1 1时且只有*的情况下 f [ i ] [ j ] [ 2 ] 1 f[i][j][2] 1 f[i][j][2]1 f [ i ] [ j ] [ 3 ] f[i][j][3] f[i][j][3]表示由符合规范的超级括号序列* 组成的方案数以后面的S进行分类前面的子串形式可以是AAB因此可以枚举S和前面的分界点 k k k f [ i ] [ j ] [ 3 ] ∑ k i j − 1 ( f [ i ] [ k ] [ 0 ] f [ i ] [ k ] [ 1 ] ) × f [ k 1 ] [ j ] [ 2 ] f[i][j][3]\sum_{ki}^{j-1}(f[i][k][0]f[i][k][1]) \times f[k1][j][2] f[i][j][3]∑kij−1(f[i][k][0]f[i][k][1])×f[k1][j][2] f [ i ] [ j ] [ 4 ] f[i][j][4] f[i][j][4]表示由* 符合规范的超级括号序列组成的方案数以前面的S进行分类前面的子串形式可以是AAB因此可以枚举S和后面的分界点 k k k f [ i ] [ j ] [ 4 ] ∑ k i j − 1 f [ i ] [ k ] [ 2 ] × ( f [ k 1 ] [ j ] [ 0 ] f [ k 1 ] [ j ] [ 1 ] ) f[i][j][4]\sum_{ki}^{j-1} f[i][k][2] \times (f[k1][j][0]f[k1][j][1]) f[i][j][4]∑kij−1f[i][k][2]×(f[k1][j][0]f[k1][j][1])
时间复杂度
状态数为 n × n × 5 n\times n\times5 n×n×5状态计算需要枚举分界位置时间复杂度最大为 O ( n ) O(n) O(n)
总的时间复杂度为 O ( 5 × n 3 ) 625 , 000 , 000 O(5\times n^3)625,000,000 O(5×n3)625,000,000由于枚举区间起点和分界位置的时间复杂度要低于 O ( n ) O(n) O(n)刚好可以AC。
代码实现
#include iostream
using namespace std;
typedef long long LL;
const int N 510, MOD 1e9 7;
char s[N];
/*
f[i][j][0]表示由单独的符合规范的序列组成的方案数
f[i][j][1]表示由并排的符合规范的序列组成的方案数
f[i][j][2]表示仅由*组成的方案数
f[i][j][3]表示由符合规范的序列 *组成的方案数
f[i][j][4]表示由* 符合规范的序列组成的方案数
*/
int f[N][N][5];
//判断a和b是否匹配
bool is_match(char a, char b)
{return a b || a ?;
}
int main()
{int n, m;cin n m;cin s 1; //字符串下标从1开始//枚举区间长度for(int len 1; len n; len ){//枚举区间开始位置for(int i 1; i len - 1 n; i ){int j i len - 1; //结束位置if(len 1) //区间长度为1{//只有1个星号if(is_match(s[i], *)) f[i][j][2] 1;}else{//计算状态[0]由单独的符合规范的序列组成的方案数if(is_match(s[i], () is_match(s[j], ))){//当长度为2时也就是只有括号的情况下子串为空if(len 2) f[i][j][0] 1;//[0] [0] [1] [2] [3] [4]for(int k 0; k 5; k )f[i][j][0] (f[i][j][0] f[i 1][j - 1][k]) % MOD;}//计算状态[2]仅由*组成的方案数if(len m is_match(s[i], *))f[i][j][2] f[i 1][j][2];//枚举分界位置计算其它状态[1]、[3]、[4]for(int k i; k j; k ){f[i][j][1] (f[i][j][1] (f[i][k][0] (LL)f[i][k][1] f[i][k][3]) * f[k 1][j][0]) % MOD;f[i][j][3] (f[i][j][3] (f[i][k][0] (LL)f[i][k][1]) * f[k 1][j][2]) % MOD;f[i][j][4] (f[i][j][4] f[i][k][2] * ((LL)f[k 1][j][0] f[k 1][j][1])) % MOD;}}}}cout (f[1][n][0] f[1][n][1]) % MOD;return 0;
}
