#4741. 「KTSC 2019 R1」广播站 题解

题目理解

这是一个动态规划优化问题：在一条直线上有 $N$ 个广播站，需要选择 $h$-集中站并分配广播范围，使得所有广播站能在 $h$ 步内将信号传到集中站，同时最小化广播范围的平方和。

关键约束：

• $h$-集中站不广播（$r=0$）
• 信号最多经过 $h$ 次传递到达集中站
• 成本是各站广播范围的平方和

核心算法

算法标签：区间动态规划 记忆化搜索 分治优化 四维状态设计

1. 算法框架

状态设计

代码使用了四种互递归的DP函数：

int F(int x, int l, int r);   // 从左向右覆盖区间[l,r]，步数限制x
int G(int x, int l, int r);   // 从右向左覆盖区间[l,r]，步数限制x  
int F2(int x, int l, int r);  // 辅助函数，处理F中的特殊情况
int G2(int x, int l, int r);  // 辅助函数，处理G中的特殊情况

状态含义：

• x：剩余的步数限制
• l, r：当前处理的区间左右边界
• 返回值：覆盖该区间的最小成本

2. 状态转移分析

F函数（从左向右）

int F(int x, int l, int r) {
    if (l == r) return 0;
    // 选项1：l单独覆盖右边
    res = F(x, l + 1, r) + (a[l] - a[r])^2;
    // 选项2：在k处分割，左边用x-1步，右边用x步
    for (int k = l; k <= r; k++)
        cmin(res, F(x - 1, l, k) + F2(x, k, r));
}

G函数（从右向左）

int G(int x, int l, int r) {
    if (l == r) return 0;
    // 选项1：r单独覆盖左边  
    res = G(x, l, r - 1) + (a[l] - a[r])^2;
    // 选项2：在k处分割，左边用x步，右边用x-1步
    for (int k = l; k <= r; k++)
        cmin(res, G2(x, l, k) + G(x - 1, k, r));
}

F2和G2函数（处理跨越分割）

处理区间两端点需要相互覆盖的情况，成本为两端点距离的平方。

3. 主算法流程

void stations(std::vector<int> X) {
    // 初始化
    n = X.size();
    for (int i = 1; i <= n; i++) a[i] = X[i-1];
    
    // 计算每个h的答案
    for (int h = 1; h < n; h++) {
        int now = INF;
        // 枚举集中站位置j
        for (int j = 1; j <= n; j++) {
            // 集中站将序列分成左右两部分
            cmin(now, F(h, 1, j) + G(h, j, n));
        }
        ans[h-1] = now;
    }
    answer(ans);
}

算法正确性分析

为什么这样设计状态？

1. 序列分割：集中站将序列分成左右两部分
2. 方向性覆盖：F处理从左到右的覆盖，G处理从右到左的覆盖
3. 步数分配：通过x参数控制信号传递的深度
4. 成本计算：平方成本符合题目要求

关键观察

• 最优解中，每个广播站的覆盖范围刚好覆盖到需要它传递的下一个站
• 通过枚举分割点，找到最优的覆盖结构
• 互递归设计避免了重复计算和复杂的状态转移

复杂度分析

• 状态数量：$O(N^3)$（三个维度：x, l, r）
• 单状态转移：$O(N)$（枚举分割点）
• 总复杂度：$O(N^4)$，在 $N \leq 120$ 时可行（约 $2\times 10^8$ 次操作）

算法标签总结

主要标签

• 区间DP - 核心算法框架
• 记忆化搜索 - 实现方式
• 互递归设计 - 创新状态设计

技术标签

• 四维状态 - F, G, F2, G2 四种状态函数
• 分治策略 - 通过分割点分解问题
• 最优化剪枝 - cmin函数进行最优性更新

动态规划标签

• 状态转移 - 复杂的多路径转移
• 边界处理 - 处理单点区间情况
• 最优子结构 - 利用问题的最优子结构性质

优化标签

• 记忆化 - 避免重复计算
• 对称性利用 - F和G函数的对称设计
• 问题分解 - 将原问题分解为子区间问题

关键创新点

1. 互递归状态设计：通过四个相互调用的DP函数处理复杂的覆盖关系
2. 方向性处理：分别处理从左向右和从右向左的覆盖
3. 集中站枚举：通过枚举集中站位置，将问题分解为两个独立子问题
4. 步数分配：通过x参数精细控制信号传递的深度限制

样例验证

对于样例2（$N=5$, 位置 $1,3,4,6,9$）：

• $h=1$ 时，需要一次覆盖所有站，成本为 $(9-1)^2 = 64$，但实际计算得到 $39$（通过更优的多站覆盖）
• $h=2$ 时，找到更优解 $18$（如题目描述）
• 算法通过枚举所有可能的集中站位置和覆盖方案找到这些最优值

这个解法通过精巧的区间DP设计和互递归状态转移，解决了复杂的广播站覆盖优化问题。