#BZOJ3982. Stacking Plates

Stacking Plates

题目描述

盘子装运公司是一家网络零售商,顾名思义,是一家只销售盘子的公司。该公司销售的盘子由不计其数的生产厂商提供,品种是全宇宙最多的,为此公司的员工倍感自豪。
在最近的一次成本分析中,公司员工发现,他们花费了大量金钱在盘子的装箱环节。一部分原因是盘子在被运输工具运走前,需要被堆成一堆。很显然,这个阶段较预期浪费了大量的时间。或许你可以为公司提供帮助。
一次装运的盘子由若干厂商生产的盘子组合而成。各家厂商将其生产的盘子从小到大堆成一堆(小盘在上,大盘在下),再运送到公司。我们称上述按照顺序排列的盘堆顺序合理。为了方便装运,你必须将来自各个厂商的盘子重新组合成顺序合理的一堆。将来自各厂商的盘堆组合成一个盘堆时,可以进行如下两种操作:
拆分(Split):可以将一个盘堆堆顶任意数目的盘子抬起,并放置在原堆的一侧,使堆一分为二。
合并(Join):可以将一个盘堆放置在另一堆的堆顶,前提是在上方的堆最底层的盘子尺寸不大于在下方的堆最顶层的盘子尺寸。
注意不能将一个盘堆堆顶上的若干盘子直接移动到另一个盘堆的堆顶,必须先拆分,后合并。给定盘堆若干,你需要求出将这些盘堆通过两种操作合并成一堆的最少次数。下面的图是对输入输出样例的解释。

输入格式

本题有多组输入数据。每组输入的第一行只有一个整数n,表示盘堆的数目,接下来的n行是对每个盘堆的描述,第i+1行的第一个整数hi为第i个盘堆的盘子数,之后有hi个正整数,为盘堆从上至下各个盘子的直径(直径为不超过10000的正整数),这些整数保证按照从小到大的顺序排列。

输出格式

对于每组数据,输出数据编号以及将n个盘堆按照规则合并为一个盘堆的最少操作次数。

2
3 1 2 4
2 3 5
3
4 1 1 1 1
4 1 1 1 1
4 1 1 1 1
Case 1: 5
Case 2: 2

数据范围与约定

H<=50,数据组数<=400