UOJ Logo

NOI.AC

#72. 外星人入侵

统计

外星人入侵

【问题描述】

8012年由实验舱自主研发的第一架高科技飞船成功驶入太空。但是很意外的是这架满载高科技精华的飞船遭受到了外星人的攻击。 外星人的部队分成 n 组,第 i 组有 ai 的战斗力,外星人的战斗力数值可以看成是一个序列 $a_1$, $a_n$, $\cdots$,$a_n$。 你可以使用SR所提供的超级武器对外星人展开攻击,每次可以选择序列中相邻的两个外星人部队 (必须选择两个),并对它们实施打击。实施打击后外星人部队的战斗力将减去 1。 现在主要的麻烦是,当外星人的战斗力减少到-1时,他们会发生自爆摧毁地球,所以无法对他们实施最后一击。作为选手的你需要不断使用超级武器,直到不能再使用为止 (不能让外星人自爆)。 研究表明,超级武器对外星人的攻击方案对能够实施攻击的次数是有影响的。为了评估对外星人实施打击的效果, SR 希望你计算实施攻击的最少次数或最大次数。

【输入格式】

第一行两个数n,type,代表外星人的部队组数以及询问类型。Type=0,询问最少次数,type=1询问最大次数。 第二行n个整数,分别表示$a_1$, $a_n$, $\cdots$,$a_n$。

【输出格式】

输出一行,分别是实施攻击的最小或最大次数。

【输入样例1】

    5 0
    1 2 1 1 3

【输出样例1】

2

【输入样例2】

    5 1
    1 2 1 1 3

【输出样例2】

3

【样例解释】

打1-2,2-3,4-5,剩下0,0,0,0,2,无法攻击。 打1-2,3-4,剩下0,1,0,0,3, 无法攻击。

【数据规模】

对于前20%数据: n ≤ 10;

对于前40%数据: n ≤ 1000;

对于前100%数据: 1 ≤ n ≤ $10^6$, 0 ≤ ai ≤ $10^9$。

在后60%数据中有20%数据满足: (∑1≤i≤n ai) ≤ $10^6$;

每个部分都有一半数据询问最小次数,另一半数据询问最大次数。

记得开$%lld%I64d$(看评测机器)以及建议使用读入优化。