「PA 2020」Elektrownie i fabryki 题解

算法思路

本题使用动态规划结合树状数组优化来解决电网连接问题。核心思想是通过维护前缀和的最优解来找到最小连接成本。

关键观察

1. 问题转化

电网连接问题可以转化为：

• 需要确保每个工厂都能连接到某个发电厂
• 总电力供应要满足总需求：$\sum a_i \geq 0$
• 最小化连接线路总长度

2. 前缀和性质

定义前缀和 $s_i = \sum_{j=1}^i a_j$，则：

• $s_n \geq 0$ 是问题有解的必要条件
• 对于位置 $i$ 和 $j$ ($i < j$)，如果 $s_i \leq s_j$，则区间 $[i+1, j]$ 的净电力非负

代码解析

前缀和计算与离散化

cin >> n;
for (int i = 1; i <= n; i++)
    cin >> a[i], s[i] = s[i - 1] + a[i];

vector<ll> X;
for (int i = 0; i <= n; i++)
    X.push_back(s[i]);

// 检查总电力是否足够
if (s[n] < 0) {
    cout << "-1\n";
    return 0;
}

// 离散化前缀和以便树状数组处理
sort(X.begin(), X.end());
for (int i = 0; i <= n; i++)
    s[i] = lower_bound(X.begin(), X.end(), s[i]) - X.begin() + 1;

动态规划与树状数组优化

struct BIT {
    int c[N];
    void add(int x, int v) {
        while (x <= n + 1) {
            c[x] = min(c[x], v);  // 维护最小值
            x += x & -x;
        }
    }
    
    int qry(int x) {
        int ret = 1e9;
        while (x) {
            ret = min(ret, c[x]);
            x -= x & -x;
        }
        return ret;
    }
} bit;

// 初始化
fill(bit.c + 1, bit.c + n + 2, 1e9);
bit.add(s[0], f[0] - 0);  // 初始状态

// 动态规划转移
for (int i = 1; i <= n; i++) {
    f[i] = bit.qry(s[i]) + i - 1;
    bit.add(s[i], f[i] - i);
}

算法正确性

状态定义

$f[i]$ 表示处理到第 $i$ 个城市时的最小成本。

状态转移

对于位置 $i$，寻找最近的 $j < i$ 使得 $s_j \leq s_i$，然后：

这表示从 $j$ 到 $i$ 需要连接线路，成本为距离 $i - j - 1$。

树状数组优化

树状数组维护对于每个前缀和值 $s$ 的最小 $f[j] - j$，这样可以在 $O(\log n)$ 时间内找到最优的 $j$。

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 离散化：$O(n \log n)$
  • 动态规划：$O(n \log n)$
• 空间复杂度：$O(n)$