Zth's Blog

记录学习路上的点滴

0%

2022杭电杯超级联赛(4)

发表于 分类于

比赛链接

1001(括号序列， 区间dp)

题目

题目链接

题目描述

给出一个长度为$n$的括号序列$A$， 括号有$m$种(类似于大小中括号， 只能同种括号之间匹配)

其中$A_i > 0$表示位置$i$上是一个种类为$A_i$的左括号， $A_i < 0$表示位置$i$上是一个种类为$|A_i|$的右括号， $A_i = 0$表示此处的括号可以由你指定种类和左右

问有多少种指定方案使得这个序列是一个合法的括号序列

数据范围

多组数据， $T \leq 20$

$1 \leq n \leq 500, 1 \leq m < 10^9 + 7$

$|A_i| \leq m$

时间限制

$3000ms$

题解

首先很容易想到区间$dp$， 比赛时我的第一反应也是这样， 但是一想数据范围是$T \times n^3$， 达到了$10^9$级别， 肯定过不了， 就没接着往下想， 但是事实证明其实能过

那区间$dp$思路就比较显然了， 设$g[l][r]$表示区间$[l, r]$的合法方案数量， 区间$[l, r]$至少能被分成两段合法的括号序列(如果$A_l$和$A_r$进行了匹配， 那么我们认为这两段是空集和$[l, r]$)

那我们是不是只要枚举一下这两段的分割点然后统计答案就可以了

这样是不对的， 因为有算重的方案， 下面举个例子

()()()

对于这个序列而言， 两段可以是$[1, 2], [3, 6]$也可以是$[1, 4], [5, 6]$， 但这其实是一种， 所以上述转移方程是不对的

那我们应该怎么转移呢？ 还是区间$[l, r]$至少能被分成两段这个思路， 只不过我们强制让$A_r$和$A_{k + 1}$进行匹配， 这样就不会重复了， 设$f[i][j]$表示$A_i$和$A_j$匹配的限制下区间$[l, r]$的合法方案数量， 那么有

设$mul$为$A_l$和$A_r$匹配的方案数， 那么有

$dp$时当前处理区间长度为最外层循环$len$， 内层为左端点$l$， 处理时先处理$f$处理$g$(因为计算$g$时需要当前$len$层的$f$， 而计算$f$需要的是上一层$len - 1$的$g$)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cstring>

const int mod = 1e9 + 7;

int t;
int n;
long long m;
int a[512];
long long f[512][512], g[512][512];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));

        scanf("%d%lld", &n, &m);
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);

        for(int i = 0; i <= n; i ++) g[i + 1][i] = 1;

        for(int len = 2; len <= n; len += 2)
        {
            for(int l = 1; l + len - 1 <= n; l ++)
            {
                int r = l + len - 1;
                long long mul = 0;

                if(a[l] >= 0 && a[r] <= 0)
                {
                    if(a[l] == 0 && a[r] == 0)
                        mul = m;
                    else if(a[l] == 0 || a[r] == 0)
                        mul = 1;
                    else if(a[l] + a[r] == 0)
                        mul = 1;
                }

                f[l][r] = g[l + 1][r - 1] * mul % mod;

                for(int k = l; k <= r; k += 2) g[l][r] = (g[l][r] + g[l][k - 1] * f[k][r]) % mod;
            }
        }

        printf("%lld\n", g[1][n]);
    }

    return 0;
}