「USACO 2023.1 Platinum」Mana Collection 题解

题目大意

有 $N$ 个法力池，第 $i$ 个池子每秒产生 $m_i$ 单位法力。池子之间通过有向边连接，每条边有移动时间。Bessie 可以在任意时刻清空所在池子的法力。给定 $Q$ 个查询，每个查询要求在第 $s$ 秒结束时必须在池子 $e$ 的情况下，能收集的最大法力值。

解题思路

核心观察

1. 法力收集的线性性：每个池子的法力值与时间成正比
2. 状态压缩：由于 $N \leq 18$，可以用位掩码表示访问过的池子集合
3. 最优子结构：最终法力值 = 总时间 × 总产生速率 - 路径移动代价

算法步骤

1. 预处理最短路径

使用 Floyd 算法计算所有点对之间的最短距离：

for (int k = 1; k <= n; ++k)
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

2. 状态压缩动态规划

定义：

• f[s][i]：访问集合 s 中的池子，最后在池子 i 的最小移动代价
• sum[s]：集合 s 中所有池子的法力产生速率之和

状态转移：

f[s | (1 << j - 1)][j] = min(f[s | (1 << j - 1)][j], 
                             f[s][i] + dis[i][j] * sum[s]);

3. 查询处理优化

对于每个终点池子 $e$，我们处理所有以 $e$ 为终点的查询。

对于状态 (s, e)，法力值计算公式为：

法力值 = sum[s] * s - f[s][e]

这可以看作直线：y = k * x + b，其中：

• k = sum[s]（斜率）
• b = -f[s][e]（截距）

使用李超线段树维护这些直线，快速回答查询。

关键代码解析

李超线段树

void ins(ci p, ll K, ll B) {
    // 在区间中插入直线 y = K*x + B
    // 维护区间内每个 x 对应的最大 y 值
}

ll qry(ci p, ci pos) {
    // 查询位置 pos 的最大 y 值
}

查询处理

for (int i = 1; i <= n; ++i) {
    // 收集所有以 i 为终点的查询
    for (auto tmp : vec[i])
        x[++len] = tmp.first;
    
    // 对每个状态 (s, i)，插入直线
    for (int s = 0; s < 1 << n; ++s)
        if (f[s][i] != inf)
            ins(1, sum[s], -f[s][i]);
    
    // 回答查询
    for (auto tmp : vec[i])
        ans[tmp.second] = qry(1, lower_bound(...) - x);
}

复杂度分析

• Floyd 算法：$O(N^3)$
• 状态压缩 DP：$O(2^N \cdot N^2)$
• 查询处理：$O(2^N \cdot N + Q \log Q)$

由于 $N \leq 18$，$2^N \approx 2.6 \times 10^5$，在可接受范围内。

样例解释

对于样例1：

• 池子1：1单位/秒，池子2：10单位/秒
• 查询 100 2 的答案 1090：
  • 在池子1待90秒：90 × 1 = 90
  • 移动到池子2（10秒）
  • 在池子2待100秒：100 × 10 = 1000
  • 总计：90 + 1000 = 1090

总结

本题综合运用了：

1. 图论：多源最短路径（Floyd）
2. 动态规划：状态压缩DP
3. 数据结构：李超线段树优化查询
4. 数学：将问题转化为直线求最大值

这种将组合优化问题转化为几何问题的方法，在处理带时间因素的收集类问题时非常有效。