#P14112. [ZJCPC 2017] Sequence to Sequence
[ZJCPC 2017] Sequence to Sequence
题目描述
Chiaki has a sequence . She would like to change it to another sequence using the following operations:
- choose two indices and (), and add to every nonzero element between the indices and (both inclusive).
- choose two indices and (), and subtract from every nonzero element between the indices and (both inclusive).
Chiaki would like to know the minimum number of operations needed.
输入格式
There are multiple test cases. The first line of input contains an integer , indicating the number of test cases. For each test case:
The first line contains an integer () -- the length of the sequence.
The second line contains integers ().
The third line contains integers ().
It is guaranteed that the sum of over all test cases does not exceed .
输出格式
For each test case, output an integer denoting the minimum number of operations. If it is impossible to change the sequence, output instead.
2
5
1 1 1 1 1
2 0 2 0 2
7
3 1 2 3 2 1 4
2 0 0 0 0 0 2
3
3
提示
For the first test case: $\{1,1,1,1,1\} \xrightarrow{[2,2],\ -1} \{1,0,1,1,1\} \xrightarrow{[4,4],\ -1} \{1,0,1,0,1\} \xrightarrow{[1,5],\ +1} \{2, 0, 2, 0, 2\}$.