• [D] Greedy Amunu

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • 省赛临近了,Amunu觉得自己不能再松懈了,便开始奋进。NOJ里有很多题目,她决定开始做这些题目。
    但是题目有难题和水题之分,她便给这些题目分级,当她看到这题是水题时,觉得没兴趣做就不做了,当她觉得这题是难题时,她便疯狂的多做几次。
    现在,她知道了所有题目的难度,但是即使这样也不好分划到底这题该做几次呢。所以她在做题前变随便写了串数字,每个数字在1到9之间,包括1和9,表示对应题目的必做次数。
    例如:12428789一共8题
    表示的意思是第一题做1次就够,第2题做2次就够,...,最后一题做9次就够,但是做题顺序可以随意。
    但是她还有个习惯,就是当她选择要做第N题的时候,她会把第N题相邻的两题也作一遍,我们定义这样算是选择一次(做三题)。
    但是当第N题的做题次数已经达到要求时,就不能再选择这题,例如:424,当两次都选择做第二题时,那么每题的做题次数是222,第二题已经达到了做题要求,所以她不能再选择第二题来做。也就是说当她选择第N题时,第N题必须还未达到次数要求,但是相邻的两题没有限制,只是当相邻的两题已经达到要求时她可以不去做相邻的两题。

    现在告诉你Amunu的数字串,她至少要选择几次才能达到所有题目的要求次数?

  • 输入
  • 第一行是题目数量 N (1 <= N <= 100)。
    第二行有N个数表示对于题目要做的次数。
  • 输出
  • 问Amunu至少要选择几次才能达到所有题目的要求次数?
  • 样例输入
  • 4
    3 1 4 2
    
  • 样例输出
  • 6
    
  • 提示
  • 来源
  • Hungar
  • 操作

显示春菜