레이팅 미적용베시는 거대한 충격파를 만들어 낼 수 있는 강력한 발굽 임플란트를 실험하고 있다. 그녀 앞에는 타일 \(N\)개(\(2 \leq N \leq 10^5\))가 일렬로 놓여 있으며, 각 타일을 부수려면 각각 최소 \(p_0,p_1,\dots,p_{N-1}\)의 힘이 필요하다(\(0 \leq p_i \leq 10^{18}\)).
베시는 특정 타일을 내리쳐서 힘을 가할 수 있지만, 임플란트의 기묘한 특성 때문에 그녀가 내리친 타일에는 힘이 전혀 가해지지 않는다. 대신 \([0,N-1]\) 범위의 정수 \(x\)에 대해 타일 \(x\)를 한 번 내리치면, \([0,N-1]\) 범위의 모든 정수 \(i\)에 대해 타일 \(i\)에 \(|i-x|\)의 힘이 가해진다. 이 힘은 누적되므로, 어떤 타일에 \(2\)의 힘을 두 번 가하면 그 타일에는 총 \(4\)의 힘이 가해진다.
모든 타일을 부수기 위해 필요한 최소 타격 횟수를 구하시오.
Problem credits: Suhas Nagar
배점
- 입력 2: 모든 \(p_i\)가 같다.
- 입력 3-6: \(N\le 100\)
- 입력 7-14: 추가 제약이 없다.
Problem credits: Suhas Nagar
첫째 줄에 테스트 케이스의 수를 나타내는 \(T\)(\(1 \leq T \leq 100\))가 주어진다.
\(2t\)번째 줄에 테스트 케이스 \(t\)의 타일 수인 정수 \(N\)이 주어진다.
\(2t+1\)번째 줄에 타일 \(i\)를 부수는 데 \(p_i\)의 힘이 필요함을 나타내는, 공백으로 구분된 \(N\)개의 수 \(p_0,p_1, \ldots, p_{N-1}\)이 주어진다.
하나의 입력에서 모든 \(N\)의 합은 \(5\cdot 10^5\)를 넘지 않음이 보장된다.
\(T\)개의 줄을 출력한다. \(i\)번째 줄에 \(i\)번째 테스트 케이스의 답을 출력한다.
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 10000000000000000002
3
2
4
4
2000000000000000000For the first test, the only way for Bessie to break all the tiles with two
punches is to punch \(0\) twice, applying total powers of \([0,2,4,6,8]\)
respectively.
For the second test, one way for Bessie to break all the tiles with three
punches is to punch \(0\), \(2\), and \(4\) one time each, applying total powers of
\([6,5,4,5,6]\) respectively.
For the third test, one way for Bessie to break all the tiles with two punches
is to punch \(0\) and \(1\) one time each, applying total powers of \([1,1,3,5,7]\)
respectively.
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Platinum