P2438 [SDOI2005]解环

    • 35通过
    • 63提交
  • 题目提供者 gryql
  • 评测方式 云端评测
  • 标签 各省省选 2005 山东
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    拜特兰并不总是一个非常民主的国家,也有一些阴暗的历史。一个美好的日子,拜特将军(该国的统帅)作了一个用以结束长期内战的决定,释放被关押的反对派。然而,他并未让反对派的领袖拜特萨直接自由,而是用一根“拜特链”将拜特萨锁在墙边.该链子由很多环和固定在墙上栅栏组成。尽管环并未和栅栏融合在一起,但想除去它们却非常困难。

    “将军,你为什么要用链子将我锁在墙边而不让我自由!”拜特萨大叫道。

    “拜特萨,你并未完全被链子锁住,我可以坦率的告诉你,你完全可以从栅栏上解下环。”拜特将军回答,同时他补充说,“但是,你必须在夜里工作,一个小时之内完成,不能弄出任何声音,否则,我将按有关法律治罪。”

    题目描述

    为了帮助拜特萨!链子上的环按整数1,2,…,n进行了编号。我们可以按照以下规则解开环:

     只有一个环时可以被连接到栅栏或从栅栏上拆开。

     第1号环总能进行连接或拆开

     如果1,...,k-1 (1<=k<n)环都被拆开,第k个环被连接时, 此时我们能连接或拆开 第k+1个环.

    写一个程序:

    输入描述了拜特链的构成,

    计算拆除拜特链上全部环的最少操作次数,

    将结果输出。

    输入输出格式

    输入格式:

    第1行有一个整数n, 1<=n<=1 000.在第2行有n个用一个空格分隔的整数 o1,o2,...,on (每个都是0或1),如果 oi=1, 那么第I个环和栅栏相连,如果 oi=0, 那么第I环没有和栅栏相连。

    输出格式:

    只包含一个整数,为解开拜特链的全部环的最少操作次数。

    输入输出样例

    输入样例#1: 复制
    4
    1 0 1 0
    
    输出样例#1: 复制
    6
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。