Skip to content

11386: 【原1386】Scheme解释器

题目

题目描述

author: 陈天垚 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1386

Description

Scheme是一种很神奇的语言,现在我们有一些同学要写它的解释器。不过,对于现在的你来说,你要研究一些关于Scheme某种放言的问题。

这种Scheme方言的主体是函数。对于某个函数,我们现在不关心它做什么,只关心它需要多少个参数。

假设一个函数需要\(n-1\)个参数,我们就用 \[ n \] 来代表这个函数。

现在我们要研究这种语言中的“语句”。

一个语句\(E\)可以是一个函数: \[ E\;=\;n \] 也可以是一个语句作为另一个语句的参数输入后组成的新语句: \[ E\;=\;(E_1\quad E_2) \] (注:每一个语句本质上其实是一个函数,在上式中,\(E_1\)是一个语句,代表一个函数,而\(E_2\)这个语句是\(E_1\)的一个参数。) 在上式中,如果语句\(E_1\)是一个有\(m\)个参数的函数,在输入\(E_2\)作为一个参数之后,新语句\(E\)的参数个数就是\(m-1\)。

例如,语句 \[ ((4\quad 2)\quad (3\quad 5)) \] 整体代表一个\(1\)参数的函数

如果一个语句的形式是这样的: \[ (\ldots(((E_1\quad E_2)\quad E_3)\quad E_4)\quad\ldots\quad E_n) \]

那么它可以被简化成 \[ (E_1\quad E_2\quad E_3\quad\ldots\quad E_n) \]

现在,给你一个长度为\(n\)的正整数数列\({a_1,\;a_2\;\ldots\;a_n}\),问你最少加上多少对括号之后它会变成一个合法的Scheme方言语句。

Input Format

输入共有两行。

第一行一个正整数\(n\)

第二行\(n\)个正整数,表示给定的正整数数列。

Output Format

输出一行一个正整数,表示最少添加几对括号。无解输出-1

Sample Input \(1\)

5

3 2 1 3 2

Sample Output \(1\)

3

Sample Explanation \(2\)

最优方案为\((3\quad(2\quad 1)\quad(3\quad 2))\)。

Sample Input \(2\)

5

1 1 2 2 1

Sample Output \(2\)

-1

Sample Explanation \(2\)

由于第一个\(1\)代表的是一个零参数的函数,它不能有任何的输入。但是它作为数列中第一个元素,它必须要有输入,这产生了矛盾,因此无解。

Hint

对于\(40\%\)的数据,\(N\leq 100\)。

对于\(60\%\)的数据,\(N\leq 1000\)。

对于\(100\%\)的数据,\(N\leq 10^5\),\(a_i\leq N\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!