题解：P12630 [ICPC 2025 NAC] SLA Tomography

· · 题解

题解

P12630 [ICPC 2025 NAC] SLA Tomography

题目传送门

题目描述

立体光刻（SLA）是一种 3D 打印技术，通过激光逐层将液态材料固化成固体物体。在本问题中，我们将考虑 SLA 的二维简化版本，其中打印对象的设计可以表示为一个由 \texttt{\#} 和 \texttt{.} 字符组成的矩形网格，\texttt{\#} 表示被对象占据的网格单元，\texttt{.} 表示空白区域。例如，以下是一个 4 \times 8 的设计：

..#.....
..#..#..
#.#.##..
#.#####.

设计不必由单个连通块组成，但除了设计最底行的 \texttt{\#} 单元外，每个 \texttt{\#} 单元必须由正下方的另一个 \texttt{\#} 单元支撑。

使用 SLA 打印对象的过程是逐层进行的，从最底行开始。首先，该行的所有单元都被液态光敏树脂覆盖。然后激光扫描该行，将所有 \texttt{\#} 单元的树脂固化成固体，跳过所有 \texttt{.} 单元。接着，最左侧 \texttt{\#} 左侧和最右侧 \texttt{\#} 右侧的多余液态树脂会流走，其他液态树脂则会被困住。（如果某行没有 \texttt{\#} 单元 —— 这种情况只可能发生在设计顶部附近，当对象已完全打印时 —— 该行的所有液态树脂都会流走。）然后对每一后续行重复此过程。对于上面的设计，打印完成后，所有标有 \sim 字符的单元中会残留树脂：

..#.....
..#~~#..
#~#~##..
#~#####.

在手动吸除对象上残留的树脂时，你开始思考：仅通过知道打印后设计每一行残留的液态树脂量，能还原出原始设计的多少信息？对于上述设计，每一行（从设计顶部开始）的残留树脂量分别为 0、2、2、1。其他设计也可能具有相同的残留树脂特征；例如：

....
#..#
#..#
#.##

给定每一行（从顶行开始）残留液态树脂单元的数量列表，输出满足这些残留量的最窄对象设计的宽度。如果不存在这样的设计，输出 \texttt{impossible}。

输入格式

第一行输入包含一个整数 N（1 \leq N \leq 10^5），表示对象设计的行数。\ 接下来 N 行，每行包含一个整数 x（0 \leq x \leq 10^9），表示期望对象设计每一行（从顶行到底行）的残留液态树脂单元数量。

至少有一行的残留液态树脂单元数量大于零。

输出格式

输出满足输入残留量的最窄对象设计的宽度（列数）。（"最窄" 指列数尽可能少。）如果不存在这样的设计，输出 \texttt{impossible}。

简化题意

即构造一个可以使每一层都能容纳下题目要求的格子数量的一个类似“碗”或者“箱子”的结构：

例如：

........................
#.......#.......#......#
##.....#####...###.....#
####..#######.#####....#
####.###############..##

那么可以容纳的位置就是

这些红圈圈内的地方。

并且要求构造出来的结构最窄，然后输出该宽度。

思路

由题可得该结构中的 \texttt{\#} 只能搭在另外一个 \texttt{\#} 上面，不能架空，所以每一层容纳的数量必然是从下层往上层单调不递减的。

那么如果遇到下层比上层容纳的多的话，就不能接在这里的下层了，只能再重新在旁边构造一个结构，那么宽度就会增加。

为了保证宽度最小，我们尽量让尽可能多的层叠在一起，遇到递增的再开一个新的结构增加宽度即可。

那么直接枚举一遍，时间复杂度 O(n)。

代码很短 awa

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100000+10;
int n;
int w[maxn];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>w[i];
    int sum=1;
    for(int i=1;i<=n;i++)
    {
        if(w[i]>w[i-1]) sum+=w[i]-w[i-1]+1;
    }
    cout<<sum;
    return 0;
}

温馨提醒：不开（）（）见祖宗。