「KTSC 2022 R2」安全系统 题解

问题分析

我们需要在 $N×N$ 的网格中选择一些激光传感器激活，使得：

• 激活传感器的权重和最大
• 所有激活传感器的激光路径不相交（包括端点）

激光有四个方向：

• 0: 向上 (原题中的1)
• 1: 向右 (原题中的2)
• 2: 向下 (原题中的3)
• 3: 向左 (原题中的4)

核心思路：划分枚举与动态规划

关键观察

$1.$ 区域划分：任何不相交的激光集合都会将网格划分为多个不相交的区域

$2.$ 方向约束：不同方向的激光有特定的空间关系

$3.$ 前缀最大值：可以利用DP计算各个方向的前缀/后缀最大值

算法框架

int max_level(vector<int> X_, vector<int> Y_, vector<int> D_, vector<int> W_) {
    // 初始化数据
    n = X_.size();
    For(i, 1, n) X[i] = X_[i-1], Y[i] = Y_[i-1], D[i] = D_[i-1]-1, W[i] = W_[i-1];
    
    // 按方向分类传感器
    For(i, 1, n) pos[D[i]].push_back(i);
    
    // 计算每个位置的最大权重
    For(i, 1, n) Max(a[D[i]][X[i]][Y[i]], W[i]);
    
    // 计算四个方向的DP值
    compute_dp_values();
    
    // 处理横向和纵向划分
    process_horizontal_vertical();
    
    // 处理九宫格划分情况
    process_nine_grid();
    
    return ans;
}

详细算法步骤

1. 预处理每个方向的最大值

// 计算每个方向的前缀/后缀最大值
For(i, 1, n) For(j, 1, n) {
    Max(a[2][i][j], a[2][i][j-1]);  // 向下方向的前缀最大值
    Max(a[3][i][j], a[3][i-1][j]);  // 向左方向的前缀最大值
}

Rep(i, n, 1) Rep(j, n, 1) {
    Max(a[0][i][j], a[0][i][j+1]);  // 向上方向的后缀最大值
    Max(a[1][i][j], a[1][i+1][j]);  // 向右方向的后缀最大值
}

2. 计算四个角落的DP值

// 计算从四个角落出发的最大权重和
For(i, 1, n) For(j, 1, n) {
    f[0][i][j] = max(f[0][i-1][j] + a[2][i][j], f[0][i][j-1] + a[3][i][j]);
}

For(i, 1, n) Rep(j, n, 1) {
    f[1][i][j] = max(f[1][i][j+1] + a[3][i][j], f[1][i-1][j] + a[0][i][j]);
}

Rep(i, n, 1) For(j, 1, n) {
    f[2][i][j] = max(f[2][i+1][j] + a[2][i][j], f[2][i][j-1] + a[1][i][j]);
}

Rep(i, n, 1) Rep(j, n, 1) {
    f[3][i][j] = max(f[3][i+1][j] + a[0][i][j], f[3][i][j+1] + a[1][i][j]);
}

3. 处理横向和纵向划分

// 横向划分：枚举列i作为划分线
For(i, 1, n+1) {
    For(j, 0, n) Max(ans, pre + f[2][i][j] + f[3][i][j+1]);
    // 更新前缀最大值
    int now = 0;
    For(j, 0, n) Max(now, a[2][i][j] + a[0][i][j+1]);
    pre += now;
    For(j, 0, n) Max(pre, f[0][i][j] + f[1][i][j+1]);
}

// 纵向划分：枚举行i作为划分线
For(i, 1, n+1) {
    For(j, 0, n) Max(ans, pre + f[1][j][i] + f[3][j+1][i]);
    int now = 0;
    For(j, 0, n) Max(now, a[3][j][i] + a[1][j+1][i]);
    pre += now;
    For(j, 0, n) Max(pre, f[0][j][i] + f[2][j+1][i]);
}

4. 处理九宫格划分（更复杂的情况）

// 枚举向上和向下激光作为关键划分线
for (int i : pos[0])        // 向上激光
    for (int j : pos[2])    // 向下激光
        if (X[j] - X[i] > 1 && Y[i] <= Y[j]) {
            int l = X[i] + 1, r = X[j] - 1;
            // 计算后缀最大值
            suf[r+1] = 0;
            Rep(k, r, l) suf[k] = max(suf[k+1], f[0][k][Y[i]-1] + f[2][k+1][Y[j]]);
            
            // 枚举向右激光作为第三条划分线
            for (int k : pos[1])
                if (X[k] >= l && X[k] <= r && Y[k] > Y[j]) {
                    Max(ans, suf[X[k]] + f[1][X[k]-1][Y[i]] + f[3][X[k]][Y[j]+1]);
                }
        }

算法复杂度

• 时间复杂度：$O(N^2)$
  • 预处理：$O(N^2)$
  • DP计算：$O(N^2)$
  • 划分枚举：$O(N^2)$（通过巧妙枚举关键传感器）
• 空间复杂度：$O(N^2)$

正确性证明要点

$1.$ 完备性：算法通过枚举所有可能的划分线组合，覆盖了所有不相交激光配置

$2.$ 最优子结构：DP状态正确反映了各个区域的最优解

$3.$ 无后效性：激光的方向性保证了决策的独立性

总结

本题通过划分枚举+动态规划解决了激光不相交约束下的最大权重选择问题：

$1.$ 划分枚举：枚举所有可能的网格划分线（横向、纵向、基于关键传感器）

$2.$ 方向分析：利用激光的方向特性简化问题结构

$3.$ DP优化：通过预计算各个区域的最优解，快速组合全局最优解

这种划分枚举+动态规划的方法在解决网格约束优化问题时非常有效，特别是在需要处理空间划分和方向约束的场景中。