#2392. 序列
序列
序列
题目描述
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
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 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
2
3000000000
19
样例 2
5
50
3 4 10 2 9 1 2 1 3 8 8 4 0 7 5 4 4 3 9 7 4 1 3 5 2 1 5 10 1 5 9 2 2 4 9 10 10 0 1 0 6 2 1 4 4 1 0 10 9 8
50
447 695 336 2 590 444 493 390 62 255 475 342 518 539 780 636 811 813 231 990 804 778 742 627 555 625 211 843 200 638 340 172 99 866 189 125 51 406 294 409 158 126 489 402 256 433 121 546 460 400
50
75550 27191 67304 51571 93702 73253 75829 10777 17059 27515 22693 26574 14367 80493 19171 80483 65391 41269 37192 74442 51788 12753 48233 21260 74040 55348 28429 28012 37802 57679 78844 85414 73898 36067 71039 15706 82676 26882 78480 398 78279 2578 2652 83579 87450 41858 34752 75416 28674 5165
50
8019023 5537366 3712640 65881 8182789 1656418 6208042 868619 8192211 1088079 7408191 1437405 8721109 5758336 4216057 2100721 5025651 2019965 4603268 7570330 1972209 301363 8338220 2586359 2954499 296470 7385952 2687056 460163 7692521 8748233 7394245 3810360 9368760 1309197 8458016 3157980 2164607 6609286 643236 8496312 8560715 5357875 1201496 9993418 2996563 2900344 5132504 2929954 446398
50
335477841 159436166 884500846 890946460 407636219 305568566 387448645 385086637 170781100 956879267 370172526 897049483 750671620 589570336 205810438 656410284 899743415 397182766 335895891 232988824 321713376 89186821 653079549 665493937 57262435 546475734 161859185 914734747 835998973 564684397 882644263 219015316 762491147 629148892 65455092 255377718 693137138 383262721 651628017 733846344 65958679 637584684 411940154 136806043 239594400 709227104 245877989 466217728 764610223 318872565
77
5333
567261
71740184
7111068521