시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 33 | 22 | 15 | 65.217% |
Initially, we have a given sequence a1,a2,a3,...,an. In each step, we can take any two adjacent integers ai and ai+1 and replace them with max(ai,ai+1), thus resulting in a shorter sequence. The cost of this operation is max(ai,ai+1). After n-1 such steps, the sequence length becomes 1. Given a sequence, your task is to calculate the minimal cost required to make that sequence of length 1.
The first line has a positive integer T, T <= 100,000, denoting the number of test cases. This is followed by each test case per line.
Each test case consists of two lines. The first line contains a single integer N as the length of the sequence. N is between 2 and 5000 inclusive The next line contains N integers separated by a single space. Each of the numbers in the sequence is between 1 and 100,000 inclusive.
For each test case, the output contains a line in the format Case #x: R, where x is the case number (starting from 1) and R is minimal cost to reduce the given sequence to a sequence of length 1.
10 6 15 9 8 13 19 17 7 12 15 13 8 12 9 7 8 8 12 14 10 14 18 15 13 9 12 8 3 1 1 1 5 4 7 8 1 6 4 3 2 4 1 6 8 15 16 15 10 18 22 19 22 9 14 9 14 17 21 23 18 17 14 8 13 12 11 5 1 1 6 1 6 8 4 2 1 1 1 8 9 11 12 8 10 11 6 9
Case #1: 75 Case #2: 76 Case #3: 105 Case #4: 42 Case #5: 33 Case #6: 131 Case #7: 147 Case #8: 54 Case #9: 16 Case #10: 76
ICPC > Regionals > Asia Pacific > Malaysia > Malaysia National Programming Contest > Al-Khawarizmi National Programming Contest 2010 H번