题目理解

我们有一个环形铁路，$k$ 个城市（编号 $0$ 到 $k-1$），$n$ 天的活动。每天在每个城市有一个效用值 $a_{i,t}$。

规则：

• 第 1 天从家坐火车到城市 0（算 1 次火车）
• 每天白天在当前城市获得效用
• 每天傍晚可以选择：
  • 留在当前城市（火车次数不变）
  • 坐火车到下一个城市（火车次数 +1）
• 第 $n$ 天傍晚不能坐火车
• 总效用是 $n$ 天效用之和

对于每个询问 $m$，求恰好坐 $m$ 次火车的最大总效用。

---

问题分析

关键点

• $k$ 很小（$2 \le k \le 5$），但 $n$ 很大（$10^5$）
• 这是一个带约束的路径规划问题：在时间-城市网格上找一条路径，满足火车次数限制
• 火车次数 = 移动次数 + 1（初始那次）

---

代码解法：分治 + 凸包合并

1. 状态定义

代码使用分治 DP，状态为：

array<array<POLY, 5>, 5> f;

其中：

• f[u][i] 表示在分治区间内，从城市 $u$ 开始，结束时相对于起始城市绕了 $i$ 圈（模 $k$ 意义下）的各种火车次数对应的最大效用
• POLY 是 vector<LL>，poly[x] 表示火车次数为 $x$ 时的最大效用

2. 分治框架

auto dfs = [&](auto &&dfs, auto l, auto r)->array<array<POLY, 5>, 5> {
    if (l == r) {  // 叶子节点
        for (int i : RANGE(0, k))
            f[i][0] = {a[i][l]};  // 只有1天，火车次数为0（不移动）
        return f;
    }
    
    auto mid = (l + r) >> 1;
    auto lf = dfs(dfs, l, mid), rf = dfs(dfs, mid + 1, r);
    // 合并左右子区间
};

3. 关键操作：凸包合并

auto MERGE = [](auto a, auto b) {
    // 计算差分数组（凸包斜率）
    for (auto i : RANGE(1u, n) | REVER)
        a[i] -= a[i - 1];
    for (auto i : RANGE(1u, m) | REVER)  
        b[i] -= b[i - 1];
    
    // 合并两个凸包（按斜率从大到小归并）
    decltype(a) c(n + m - 1, 0);
    c[0] = a[0] + b[0];
    merge(begin(a) + 1, end(a), begin(b) + 1, end(b), begin(c) + 1, greater());
    
    // 前缀和恢复原函数值
    for (auto i : RANGE(1u, n + m - 1))
        c[i] += c[i - 1];
    
    return c;
};

这里利用了最大效用关于火车次数是凹函数的性质，因此可以用凸包技巧高效合并。

4. 状态转移

对于左右区间 lf[u][i] 和 rf[v][j]，考虑两种连接方式：

方式1：不坐火车跨越区间边界

v = (u + i) % k;  // 左区间结束城市
auto res = MERGE(lf[u][i], rf[v][j]);
if (i + j >= k)  // 总圈数超过k，需要调整
    res.insert(begin(res), 0);
GMAX(f[u][(i + j) % k], res);

方式2：坐火车跨越区间边界

v = (v + 1) % k;  // 移动到下一个城市
auto res = MERGE(lf[u][i], rf[v][j]);
if (i + j + 1 >= k)  // 火车次数+1
    res.insert(begin(res), 0);
GMAX(f[u][(i + j + 1) % k], res);

5. 查询处理

auto res = dfs(dfs, 0, n - 1)[0];  // 从城市0开始的结果
while (q--) {
    int m; read(m); --m;  // 减去初始的1次火车
    write(res[m % k][m / k], '\n');  // 按模k分组存储
}

---

算法正确性分析

为什么是凹函数？

• 多坐一次火车可能获得更高效用，但边际效用递减
• 当火车次数足够多时，可以每天都去当天效用最高的城市，再增加火车次数不会提高效用

为什么用凸包合并？

• 两个凹函数的和还是凹函数
• 凸包合并相当于求 (f + g)(x) = max_{i+j=x} f(i) + g(j)
• 用差分+归并可以 $O(n+m)$ 完成，而不是 $O(nm)$

---

复杂度分析

• 分治深度：$O(\log n)$
• 每层合并：$O(k^4 \cdot (n+m))$，其中 $k^4$ 来自状态转移
• 总复杂度：$O(k^4 n \log n)$
• 对于 $k \le 5, n \le 10^5$，可接受

---

算法标签

• 分治 DP
• 凸包优化
• 环形结构处理
• 归并技巧

---

总结

这道题的解法非常精妙：

1. 利用 $k$ 小的特点：将状态按起始城市和模 $k$ 圈数分类
2. 分治框架：将 $n$ 天分成两半，分别求解后合并
3. 凸包优化：发现效用关于火车次数的凹性，用差分+归并高效合并
4. 环形处理：通过模 $k$ 运算自然处理环形移动

核心思想是将 $O(n^2)$ 的 DP 通过分治和凸包优化降到 $O(n \log n)$，充分利用了问题的特殊结构。