A5921 | $「ZJOI2020」序列$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

Bob 喜欢序列。 有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。每一步你可以从以下三种操作中选择一种执行： - 选择一个区间 $[l, r]$，将下标在这个区间里的所有数都减 $1$。 - 选择一个区间 $[l, r]$，将下标在这个区间里且下标为奇数的所有数都减 $1$。 - 选择一个区间 $[l, r]$，将下标在这个区间里且下标为偶数的所有数都减 $1$。 求最少需要多少步才能将序列中的所有数都变成 $0$。

第一行输入一个整数 $T$，表示数据组数。 对于每组数据，第一行输入一个整数 $n$，接下来一行输入 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。

输出 $T$ 行，对于每组测试数据，输出一行一个整数，表示答案。

输入 #1

3
5
2 1 2 1 2
8
1000000000 1000000000 0 1000000000 1000000000 0 1000000000 1000000000
13
1 1 4 5 1 4 1 9 1 9 8 1 0

输出 #1

2
3000000000
19

C++ 编辑器

输入

输出