페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8265
서브태스크

쇼크웨이브 1초 1024MB

문제

베시는 강력한 송곳발 이식을 실험 중에 있으며, 이 송곳발은 거대한 충격파를 생성할 수 있습니다. 그녀 앞에 N개의 타일이 일렬로 놓여 있으며, 각 타일을 부수는 데 필요한 최소 힘은 각각 p_0, p_1, …, p_{N-1}입니다. (0≤p_i≤10¹⁸)

베시는 특정 타일을 펀치함으로써 힘을 적용할 수 있습니다. 그러나 이식의 특이한 특성으로 인해 베시가 펀치한 타일에는 힘이 적용되지 않습니다. 대신, 그녀가 타일 x를 한 번 펀치하면, x가 [0, N-1] 범위에 있는 정수일 때 |i-x| 힘이 타일 i에 적용됩니다. 이 힘은 누적되므로, 타일에 2의 힘을 두 번 적용하면 총 4의 힘이 타일에 적용됩니다.

모든 타일을 부수는 데 필요한 최소 펀치 횟수를 구하세요.


입력

첫 번째 줄에는 테스트 케이스의 수 T (1≤T≤100)가 주어집니다.

그 후 각 테스트 케이스마다:

  • 첫 번째 줄에 N이 주어집니다. (타일의 개수)

  • 두 번째 줄에는 N개의 공백으로 구분된 p_0, p_1,\ …,\ p_{N-1}이 주어집니다. (각 타일이 부서지는 데 필요한 힘)

입력에서 N의 총합은 5⋅10^5을 넘지 않음을 보장합니다.


출력

각 테스트 케이스에 대해 필요한 최소 펀치 횟수를 출력하세요.


부분문제

번호 점수 조건
#120점

p_i = p_{i+1} (0 \le i \le N-2)

#230점

N\le 100

#350점

추가 제약 조건 없음


예제1

입력
6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000
출력
2
3
2
4
4
2000000000000000000

첫 번째 테스트의 경우, 베시가 두 번의 펀치로 모든 타일을 부수는 유일한 방법은 타일 0을 두 번 펀치하는 것입니다. 이를 통해 각 타일에 [0, 2, 4, 6, 8]의 힘이 적용됩니다.

두 번째 테스트의 경우, 베시가 세 번의 펀치로 모든 타일을 부수는 방법 중 하나는 타일 0, 2, 4를 각각 한 번 펀치하는 것입니다. 이때 각 타일에 [6, 5, 4, 5, 6]의 힘이 적용됩니다.

세 번째 테스트의 경우, 베시가 두 번의 펀치로 모든 타일을 부수는 방법 중 하나는 타일 0과 1을 각각 한 번 펀치하는 것입니다. 이때 각 타일에 [1, 1, 3, 5, 7]의 힘이 적용됩니다.


출처

USACO 2025 January Platinum

역링크 공식 문제집만