A5921. 「ZJOI2020」序列
编程题
NOI/NOI+/CTSC
知识点
题目描述
Bob 喜欢序列。
有一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$。每一步你可以从以下三种操作中选择一种执行：
- 选择一个区间 $[l, r]$，将下标在这个区间里的所有数都减 $1$。
- 选择一个区间 $[l, r]$，将下标在这个区间里且下标为奇数的所有数都减 $1$。
- 选择一个区间 $[l, r]$，将下标在这个区间里且下标为偶数的所有数都减 $1$。
求最少需要多少步才能将序列中的所有数都变成 $0$。
有一个长度为 $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$。
对于每组数据，第一行输入一个整数 $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
说明/提示
对于前 $10\%$ 的数据，$n\le 5, a_i\le 10$。
对于前 $30\%$ 的数据，$n\le 50, a_i\le 50$。
对于前 $50\%$ 的数据，$n\le 200, a_i\le 200$。
对于前 $60\%$ 的数据，$n\le 200, a_i\le 10^9$。
对于前 $70\%$ 的数据，$n\le 1000, a_i\le 10^9$。
对于前 $90\%$ 的数据，$n\le 10000, a_i\le 10^9$。
对于 $100\%$ 的数据，$1\le n\le 100000, 0\le a_i\le 10^9, 1\le T\le 10$。
对于前 $30\%$ 的数据，$n\le 50, a_i\le 50$。
对于前 $50\%$ 的数据，$n\le 200, a_i\le 200$。
对于前 $60\%$ 的数据，$n\le 200, a_i\le 10^9$。
对于前 $70\%$ 的数据，$n\le 1000, a_i\le 10^9$。
对于前 $90\%$ 的数据，$n\le 10000, a_i\le 10^9$。
对于 $100\%$ 的数据，$1\le n\le 100000, 0\le a_i\le 10^9, 1\le T\le 10$。