1551 - Sequence Decomposition
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 1
Solved: 1
- Description
- A sequence can be decomposed into the sum of unit impulses, but we can still decompose the sequence into the sum of gate function which defined as
For simplify we use G (a,b) to represent
, Now the question is how to decompose the sequence to maximize the minimum length of gate function. (The length of 
is b – a). For simplification, you just need to get the minimum length. - Input
- The first integer T is the number of test cases
Each case starts with a number N followed by N integers a[i]
(0<= T <= 10)
(0<= N <= 10000)
(0 <= a[i] <= 2^31)
(We ensure
) - Output
- The minimum length S
- sample input
-
2 6 2 3 4 3 3 1 5 2 2 2 2 2
- sample output
-
3 5
- hint
- The first case can be decomposed to G(1,5)+G(1,6)+G(2,5)+G(3,3), the minimum length is 1 and it can also be decomposed to G(1,3)+G(1,5)+G(2,6)+G(3,5), the minimum length is 3, so answer is 3.
The second case can be decomposed to 2*G (1, 5). - source
- He Jian | 2011 Multi-University Training Contest 8 - Host by HUST