[海淀区入门组 2025] 摧毁积木塔

Luogu
IDLGB4464
Time1000ms
Memory512MB
DifficultyP3
动态规划 DP2025北京小学活动
圣诞节的联欢活动上,还有一个拆积木塔的游戏。游戏的规则是,提供 $n$ 座积木塔,所有积木塔都是由棱长为 $1$ 的正方体积木块搭建而成,积木塔从左到右编号从 $1$ 到 $n$,第 $i$ 座塔的长和宽都是 $1$,高度为 $h_i$(恰好由 $h_i$ 个积木块搭建而成)。将积木块分为两类,如果上下左右四个方向都有相邻的积木块或地面,则称为**内部块**;否则称为**边界块**。规定摧毁积木塔的每一次操作为:摧毁当前局面下所有的**边界块**。你的任务是:计算同学们需要多少次操作才能摧毁所有积木塔中的所有积木块。 ## Input 第一行仅有一个整数 $n$($1 \leq n \leq 10^5$),第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$($1 \leq h_i \leq 10^9$),分别表示第 $i$ 座塔的大小。 ## Output 输出所需操作数以摧毁所有积木塔中的所有积木块。 [samples] ## Note 样例 1 解释:每次边界块都用红色标记。第一次操作后,还剩下四个块,第二次操作后只剩下一个。这最后一个块在第三次操作中被摧毁。 ![](https://cdn.luogu.com.cn/upload/image_hosting/u6ud8reb.png)
Samples
Input #1
6
2 1 4 6 2 2
Output #1
3
Input #2
7
3 3 3 1 3 3 3
Output #2
2
API Response (JSON)
{
  "problem": {
    "name": "[海淀区入门组 2025] 摧毁积木塔",
    "description": {
      "content": "圣诞节的联欢活动上,还有一个拆积木塔的游戏。游戏的规则是,提供 $n$ 座积木塔,所有积木塔都是由棱长为 $1$ 的正方体积木块搭建而成,积木塔从左到右编号从 $1$ 到 $n$,第 $i$ 座塔的长和宽都是 $1$,高度为 $h_i$(恰好由 $h_i$ 个积木块搭建而成)。将积木块分为两类,如果上下左右四个方向都有相邻的积木块或地面,则称为**内部块**;否则称为**边界块**。规定摧毁积木塔",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4464"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "圣诞节的联欢活动上,还有一个拆积木塔的游戏。游戏的规则是,提供 $n$ 座积木塔,所有积木塔都是由棱长为 $1$ 的正方体积木块搭建而成,积木塔从左到右编号从 $1$ 到 $n$,第 $i$ 座塔的长和宽都是 $1$,高度为 $h_i$(恰好由 $h_i$ 个积木块搭建而成)。将积木块分为两类,如果上下左右四个方向都有相邻的积木块或地面,则称为**内部块**;否则称为**边界块**。规定摧毁积木塔...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments