P6631 [ZJOI2020] Sequence

1s, 512MB

Bob likes sequences. There is a non-negative integer sequence $a_1, a_2,\cdots, a_n$ of length $n$. In each step, you may choose one of the following three operations to perform: - Choose an interval $[l, r]$, and subtract $1$ from all numbers whose indices are in this interval. - Choose an interval $[l, r]$, and subtract $1$ from all numbers in this interval whose indices are odd. - Choose an interval $[l, r]$, and subtract $1$ from all numbers in this interval whose indices are even. Find the minimum number of steps needed to make all numbers in the sequence become $0$.

The first line contains an integer $T$, which denotes the number of test cases. For each test case, the first line contains an integer $n$. The next line contains $n$ non-negative integers $a_1, a_2,\dots, a_n$.

Output $T$ lines. For each test case, output one integer per line, which is the answer.

Sample explanation $1$. Test case 1: $21212 \stackrel{1}{\longrightarrow} 1111 1 \stackrel{1}{\longrightarrow} 00000$. Test case 3: $1145141919810 \stackrel{1}{\longrightarrow} 0034030808700 \stackrel{8}{\longrightarrow} 0031000000700 \stackrel{10}{\longrightarrow}0000000000000$. Sample input and output $2$ are provided in the attached file. Constraints: For the first $10\%$ of the testdata, $n \leq 5, a_i \leq 10$. For the first $30\%$ of the testdata, $n \leq 50, a_i \leq 50$. For the first $50\%$ of the testdata, $n \leq 200, a_i \leq 200$. For the first $60\%$ of the testdata, $n \leq 200, a_i \leq 10^9$. For the first $70\%$ of the testdata, $n \leq 1000, a_i \leq 10^9$. For the first $90\%$ of the testdata, $n \leq 10000, a_i \leq 10^9$. For $100\%$ of the testdata, $1 \leq n \leq 100000, 0 \leq a_i \leq 10^9, 1 \leq T \leq 10$. Translated by ChatGPT 5