题解：P13821 「Diligent-OI R2 A」蒹葭苍苍

yezicong1104 · 2025-08-23 19:15:20 · 题解

题目描述

有 n 行空地，其中第 i 行的第 1 列到第 a_i 列都是空地。除了给定的空地以外，其他位置都是障碍物。

你需要从第 1 行最左边的格子走到第 n 行最右边的格子。但你走的过程中只能向上、下或右方向，也不能走出网格。但是可以重复走某个格子，重复走的只算一次， 求最多走几个格子。

思路

设 minx_i 为 a_i 到 a_n 的最小值，即 minx_i=\min_{i\le j \le n}\{a_i\}，在第 i 行最多经过 minx_i 个格子，因为无法往左走，所以第 i 行走的列数不能大于 minx_i。

代码

#include <iostream>
using namespace std;

int n;
int a[110];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int minx = 100;
    int ans = 0;
    for (int i = n; i; i--) {
        minx = min(minx, a[i]);
        ans += minx;
    }
    cout << ans;
    return 0;
}