「PA 2020」Programowanie współbieżne 题解

算法思路

本题使用动态规划和矩阵乘法来模拟并发程序的执行，通过状态压缩和组合优化找到全局变量的最小值。核心思想是将每个程序建模为状态转移矩阵，通过矩阵乘法组合所有可能的执行顺序。

关键观察

1. 程序执行模型

每个程序可以看作一个状态机，有 $2$ 种状态：

• 状态 $0$：未执行 $\texttt{Z}$（存储）指令
• 状态 $1$：已执行 $\texttt{Z}$（存储）指令

2. 指令类型分析

• $\texttt{W}$：加载全局变量到私有计数器
• $\texttt{Z}$：存储私有计数器到全局变量
• $\texttt{+}c$：私有计数器加 $c$
• $\texttt{-}c$：私有计数器减 $c$

代码解析

状态转移矩阵定义

using Matrix = std::array<std::array<DP, 2>, 2>;

$Matrix[a][b]$ 表示从状态 $a$ 到状态 $b$ 的最小代价向量。

基本操作矩阵

Matrix getSingle(const Op &op, bool must = false) {
    Matrix a;
    if (!must) {
        a[0][0] = a[1][1] = {0};  // 保持状态不变，代价为0
    }
    if (op.type == load) {
        a[0][1] = {inf, -op.val};  // 加载操作
    } else {
        a[1][0] = {op.val};        // 存储操作
    }
    return a;
}

矩阵乘法组合程序

Matrix operator*(const Matrix &a, const Matrix &b) {
    Matrix c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
        }
    }
    return c;
}

动态规划向量操作

DP operator*(const DP &a, const DP &b) {
    // 合并两个代价向量，找到最优组合
    std::vector<i64> c(a.size() + b.size() - 1);
    int i = 0, j = 0;
    c[i + j] = a[i] + b[j];
    
    // 使用贪心策略合并有序序列
    while (i + j + 1 < c.size()) {
        if (i + 1 < a.size() && (j + 1 == b.size() || 
            a[i + 1] - a[i] < b[j + 1] - b[j])) {
            i++;
        } else {
            j++;
        }
        c[i + j] = a[i] + b[j];
    }
    return c;
}

算法核心

1. 程序预处理

// 优化指令序列，移除冗余的加载操作
while (!curOps.empty() && curOps.back().type == load) {
    curOps.pop_back();
}

2. 分治计算

Matrix work(const std::vector<Op> &ops, int l, int r) {
    if (l == r) {
        Matrix a;
        a[0][0] = a[1][1] = {0};  // 单位矩阵
        return a;
    }
    if (r - l == 1) {
        return getSingle(ops[l]);  // 单指令矩阵
    }
    int m = (l + r) / 2;
    return work(ops, l, m) * work(ops, m, r);  // 分治合并
}

3. 最终答案计算

i64 workFinal(const std::vector<Matrix> &mat, int i) {
    auto other = product(mat, 0, mat.size(), i);  // 排除第i个程序
    i64 ans = inf;
    
    // 枚举所有可能的状态转移组合
    for (int st = 0; st < 2; st++) {
        for (int ed = 0; ed < 2; ed++) {
            for (int j = std::max(0, 1 - st - ed); 
                 j < other[!st][!ed].size() && 
                 j - 1 + st + ed < int(mat[i][st][ed].size()); j++) {
                chmin(ans, other[!st][!ed][j] + 
                      mat[i][st][ed][j - 1 + st + ed]);
            }
        }
    }
    return ans;
}

复杂度分析

• 预处理每个程序：$O(l \log l)$，其中 $l$ 是指令数量
• 矩阵乘法：$O(k^2)$，其中 $k$ 是状态数量
• 总复杂度：$O(\sum l \log l + n \cdot k^2)$

关键技巧

1. 矩阵建模：将程序执行建模为状态转移矩阵
2. 分治合并：使用分治策略高效组合程序
3. 贪心合并：在合并代价向量时使用贪心策略
4. 状态压缩：通过有限状态机简化问题