[COCI2017-2018#3] Retro 题解

· · 题解

简单的动态规划可以完成第一问

从上往下进行动态规划。设 f(i, j, k) 为到达第 i 行第 j 列， \text{\small\sf 右括号数}-\text{\small\sf 左括号数} = k 时序列的最大长度。

合法括号序列的性质：

任何后缀中 \text{\small\sf 右括号数}-\text{\small\sf 左括号数} \ge 0，因此我们要求 DP 中 k\ge 0。

优化空间的提示：

由于最终左右括号数量相等，所以 k 可以只用开 R 的一半。

DP 的起点可以是第一行非左括号的位置或炸弹的位置。对于第一行的右括号，k = 1，f 赋值为 1；对其他起点，k = 0，f 赋值为 0；

对其他位置，初始化时可以赋值一个负数。

从 f(i, j, k) 可以转移到下一行的三个相邻位置。根据下一个位置的字符，k 发生相应的变化。比如接收到一个左括号，则 k 减一。如果接收到的是括号，f 的值就加 1。

最终的答案即为 f(R, \textsf{‘M’\small所在的横坐标}, 0)。

记录节点状态以求出字典序最小的括号序列

我们发现，如果用滚动数组优化，完全有足够的空间用二进制压缩地记录下每一个 DP 状态的括号序列!

于是我们在 DP 时不仅比较长度，而且在长度相等时留意一下序列大小即可。

该算法的时间复杂度是 \mathcal O(R^2 S)，用到的空间不到 5MB，真是惊人的小！

参考实现

本题的代码非常的琐碎，请仔细阅读。

#include <bits/stdc++.h>
using namespace std;
#define validx(a) ((a) >= 1 && (a) <= s)
int r, s, sx;
char c[301][301];

// 一个 node 代表 DP 的一个状态
struct node {
    int len;
    unsigned seq[10];
    // seq 记录括号序列，每个二进制位上 0 代表 '('，1代表 ')'
    // 用 10 个 32 位整数可以存下至多 320 个括号。
    // 不用 std::bitset，因为它没有提供比较运算符。

    void init(int x, unsigned y) {
        len = x;
        memset(seq, 0, sizeof seq);
        seq[0] = y;
    }
    void set(unsigned x) {
        seq[x/32] |= 1u<<x%32;
    }
} nd[2][301][152];

// 比较括号序列的大小。
bool cmpSeq(const node &a, const node &b) {
    for(int i = (a.len-1)/32+1; i >= 0; --i) {
        if(a.seq[i] != b.seq[i]) return a.seq[i] < b.seq[i];
    }
    return 0;
};

ostream &operator<<(ostream &out, const node &x) {
    out<<x.len<<"\n";
    for(int i = x.len-1; i >= 0; --i)
        out<<(x.seq[i/32] & 1u<<i%32 ? ')' : '(');
    return out;
}

int main() {
    // ifstream cin("r:/test/retro.in");
    ios::sync_with_stdio(0);
    cin>>r>>s;
    memset(nd, -1, sizeof nd);
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= s; j++) {
            cin>>c[i][j];
        }
    // sx = 'M' 所在的横坐标
    sx = find(c[r]+1, c[r]+s+1, 'M') - c[r];
    for(int j = 1; j <= s; j++)
        if(c[1][j] == ')') {
            nd[1][j][1].init(1, 1);
        } else if(c[1][j] != '(') {
            nd[1][j][0].init(0, 0);
        }
    // 将 DP 转移中大量重复的代码写成函数，节省码量。
    // 注意：为了方便，这个函数中没有向 seq 添加新的括号。
    auto dpUpt = [](const node &cur, node &nxt, int df) -> bool {
        if(cur.len+df > nxt.len || (cur.len+df == nxt.len && cmpSeq(cur, nxt))) {
            nxt = cur;
            nxt.len = cur.len+df;
            return 1;
        }
        return 0;
    };
    for(int i = 1; i < r; ++i) {
        // 及时清空滚动数组。
        memset(nd[i+1 & 1], -1, sizeof nd[0]);
        for(int j = 1; j <= s; j++) {
            // 注意：非首行的炸弹作为起点，只能在滚动到此时进行初始化。
            if(c[i+1][j] == '*') nd[i+1 & 1][j][0].init(0, 0);
            // 只处理序列存在的节点。
            for(int k = 0; k <= r/2 && k <= i; ++k) if(nd[i & 1][j][k].len >= 0) {
                // 注意：为了方便，在新一轮 DP 开始前向 seq 中添加括号。
                // 因为二进制用 0 代表左括号，所以只用管右括号。
                if(c[i][j] == ')') {
                    nd[i & 1][j][k].set(nd[i & 1][j][k].len-1);
                }
                for(int dx: {-1, 0, 1}) if(validx(j+dx)) {
                    if(c[i+1][j+dx] == ')') {
                        dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k+1], 1);
                    } else if(c[i+1][j+dx] == '(') {
                        if(k > 0)
                            dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k-1], 1);
                    } else if(c[i+1][j+dx] != '*') {
                        dpUpt(nd[i & 1][j][k], nd[i+1 & 1][j+dx][k], 0);
                    }
                }
            }
        }
    }
    cout<<nd[r & 1][sx][0]<<endl;
    return 0;
}