TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3750
  • 题目
  • P3750奶牛拍照
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

       约翰的n(1<=n<=15)头奶牛正开心地站成一排,等待约翰拍集体照。
       在大家都长时间保持微笑,等待约翰按下快门的时候,约翰突然停了下来,因为他发现奶牛们并没有按照身高由低到高的顺序排列(每头奶牛的高度都不相同),这样的话就拍不出满意的照片,于是约翰决定调整一下奶牛们的位置。
       这下可扫了奶牛们的兴,大家决定为难一下约翰。奶牛们告诉约翰,要调整位置可以,每次只能选择连续一段奶牛出来,然后将这一段整体插入到剩下队伍的任意位置。而且要求约翰操作的次数尽可能少。
      你能否帮助约翰算算,最少几次操作就能将奶牛们调整成由矮到高的排列顺序。

    输入格式

    第一行,一个整数n,表示奶牛的数量
    第二行,n个空格间隔的整数,描述了目前奶牛排列的情况,每个整数表示对应奶牛的身高排名。

    输出格式

    一行,一个整数,表示最少需要的调整次数。
    如果次数大于4,输出"-1"

    样例输入

    6
    1 3 4 6 2 5

    样例输出

    2

    提示

    样例说明:
    1 3 4 6 2 5
    第一步,把[2 5]这一段选出,插入到4的后面,得到1 3 4 [2 5] 6
    第二步,把[2]这一段选出,插入到1的后面,得到1 [2] 3 4 5 6


    来源  改编自poj3460