#PQJ472x427. QOJ 472_427

    ID: 2989 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2020区间DP

QOJ 472_427

3 序列 3.1 题目描述 Bob 喜欢序列。 有一个长度为n 的非负整数序列a1, a2, . . . , an。每一步你可以从以下三种操作中选择一种 执行: • 选择一个区间[l, r],将下标在这个区间里的所有数都减1。 • 选择一个区间[l, r],将下标在这个区间里且下标为奇数的所有数都减1。 • 选择一个区间[l, r],将下标在这个区间里且下标为偶数的所有数都减1。 求最少需要多少步才能将序列中的所有数都变成0。 3.2 输入格式 第一行输入一个整数T,表示数据组数。 对于每组数据,第一行输入一个整数n,接下来一行输入n 个非负整数a1, a2, · · · , an。 3.3 输出格式 输出T 行,对于每组测试数据,输出一行一个整数,表示答案。 3.4 样例输入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 3.5 样例输出1 2 3000000000 19 7

3.6 样例解释1 第一组数据:21212 1 −→11111 1 −→00000 第三组数据:1145141919810 1 −→0034030808700 8 −→0031000000700 10 −→0000000000000 3.7 样例输入输出2 见下发文件 3.8 数据范围与约定 对于前10% 的数据,n ≤5, ai ≤10。 对于前30% 的数据,n ≤50, ai ≤50。 对于前50% 的数据,n ≤200, ai ≤200。 对于前60% 的数据,n ≤200, ai ≤109。 对于前70% 的数据,n ≤1000, ai ≤109。 对于前90% 的数据,n ≤10000, ai ≤109。 对于100% 的数据,1 ≤n ≤100000, 0 ≤ai ≤109, 1 ≤T ≤10。 8