题解：UVA1442 洞穴 Cav

这篇题解提供中文和英文两种版本。
This solution is available in both Chinese and English.

中文版本

我们可以扫描两次洞穴的地面和顶，分别是从左往右扫描和从右往左扫描的两次。

每次扫描我们要扫出的是一个数组，转移方式如下（以从左往右扫描为例）：

$f_0 = s_1$ ，这是初始条件。
1. 若 $f_{i-1} < p_i$ ，则 $f_i = p_i$ 。
2. 若 $f_{i-1} > s_i$ ，则 $f_i = s_i$ 。
3. 否则， $f_i = f_{i-1}$ 。

从右往左扫描也是同理的操作了。扫描完两个数组之后，计算答案的值：

\sum_{i = 1}^{n} \min(f_i, g_i) - p_i

这里的

g

数组就是从右往左扫描出来的数组。这样就解决了这道问题。

代码在英文版本下面。

English version

We can scan the floor and roof of the cave twice, from left-to-right and from right-to-left.

For each scan, we'll get an array, the transferance is as follows (using left-to-right scanning as an example) :

$f_0 = s_1$ ，that's the initial condition。
1. if $f_{i-1} < p_i$ then $f_i = p_i$ 。
2. if $f_{i-1} > s_i$ then $f_i = s_i$ 。
3. otherwise $f_i = f_{i-1}$ 。

The same goes for scanning from right-to-left. After scanning both arrays, calculate the value of the answer:

\sum_{i = 1}^{n} \min(f_i, g_i) - p_i

The

g

array here is the array scanned from right to left. That solves the problem.

Code is below here.

代码实现 Code implementation

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 1e6 + 10;
int t, n, ans, p[maxn], s[maxn], f[maxn], g[maxn];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> p[i];
        for (int i = 1; i <= n; i++) cin >> s[i];
        // left to right
        f[0] = s[1];
        for (int i = 1; i <= n; i++) {
            if (f[i - 1] < p[i]) f[i] = p[i];
            else if (f[i - 1] > s[i]) f[i] = s[i];
            else f[i] = f[i - 1];
        }
        // right to left
        g[n + 1] = s[n];
        for (int i = n; i >= 1; i--) {
            if (g[i + 1] < p[i]) g[i] = p[i];
            else if (g[i + 1] > s[i]) g[i] = s[i];
            else g[i] = g[i + 1];
        }
        // calculate the answer
        ans = 0;
        for (int i = 1; i <= n; i++) {
            int cur = min(g[i], f[i]);
            ans += cur - p[i];
        }
        cout << ans << "\n";
    }
    return 0;
}

题解：UVA1442 洞穴 Cav

文章操作