http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1481. 组合子逻辑
时间限制:1.0s   内存限制:128.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  组合子逻辑是Moses Schönfinkel和Haskell Curry发明的一种符号系统,用于消除数理逻辑中对于变量的需要。本题考察一种与真实世界的组合子演算略有差别的组合子系统。
  一个组合子项是下列形式之一:
  P
  (E1 E2)
  其中 P 表示一个基本函数,E1 以及 E2 表示一个组合子项(可以相同)。不满足以上形式的表达式均非组合子项。
  我们将一个组合子项 E 的参数个数 np(E) 如下:
  np(P)=基本函数P的参数个数;
  np((E1 E2))=np(E1)-1。
  本题中,我们用一个正整数同时表示一个基本函数,以及该基本函数的参数个数。
  对于一个组合子项 E ,如果它和它包含的所有组合子项的参数个数np均为正整数,那么我们称这个 E 为范式。
  我们经常将组合子项简化表示:如果一个组合子项E含有连续子序列 (...((E1 E2) E3) … En) (其中n≥3 ),其中 Ek 表示组合子项(可以是简化表示的),那么将该部分替换为 (E1 E2 E3 … En) ,其他部分不变,得到表达式E的一个简化表示。一个组合子项可以被简化表示多次。
  给定一个基本函数序列,问至少需要添加多少对括号,才能使得该表达式成为一个范式的简化表示(即满足范式的性质);如果无论怎样添加括号,均不能得到范式的简化表示,输出 -1 。
输入格式
  第一行包含一个正整数 T ,表示有 T 次询问。
  接下来 2T 行。
  第 2k 行有一个一个整数 n_k,表示第 k 次询问的序列中基本函数的个数。
  第 2k+1 行有 n_k 个正整数,其中第 i 个整数表示序列中第 i 个基本函数。
输出格式
  输出 T 行,每行一个整数,表示对应询问的输出结果。
样例输入
2
5
3 2 1 3 2
5
1 1 1 1 1
样例输出
3
-1
样例说明
  第一次询问:一个最优方案是(3 (2 1) (3 2))。可以证明不存在添加括号对数更少的方案。
  第二次询问:容易证明不存在合法方案。
数据规模和约定
  令 TN 表示输入中所有 n_k 的和。

测试点编号
规模
1
T≤30,n_k≤3
2
T≤30,n_k≤15
3
TN≤100
4
TN≤500
5
TN≤2000
6
TN≤5000
7
TN≤5000
8
TN≤100000
9
TN≤200000
10
TN≤200000