레이팅 미적용베시에게는 한 줄로 놓인 \(N\) (\(2\le N\le 300\))개의 타일이 있고, 순서대로 못생김 값 \(a_1, a_2, \dots, a_N\)을 가진다 (\(1\le a_i\le 10^6\)). 그중 \(K\) (\(0\le K\le \min(N,6)\))개의 타일은 제자리에 고정되어 있다. 구체적으로 인덱스 \(x_1,\dots, x_K\) (\(1\le x_1 < x_2<\dots< x_K\le N\))의 타일들이다.
베시는 타일들의 총 못생김을 최소화하고 싶다. 총 못생김은 연속한 모든 타일 쌍에 대한 못생김 최댓값의 합, 즉 \(\sum_{i=1}^{N-1}\max(a_i,a_{i+1})\)로 정의된다. 베시는 다음 연산을 몇 번이든 수행할 수 있다: 고정되지 않은 타일 두 개를 골라 서로 교환한다.
베시가 연산을 최적으로 수행할 때 얻을 수 있는 최소 총 못생김을 구하여라.
출제: Benjamin Qi
배점
- 입력 5: \(K=0\)
- 입력 6-7: \(K=1\)
- 입력 8-12: \(N\le 50\)
- 입력 13-24: 추가 제약 없음
출제: Benjamin Qi
첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 줄에 \(a_1,\dots,a_N\)이 주어진다.
다음 줄에 \(K\)개의 인덱스 \(x_1,\dots,x_K\)가 주어진다.
가능한 최소 총 못생김을 출력한다.
3 0
1 100 10110Bessie can swap the second and third tiles so that \(a=[1,10,100]\), achieving
total ugliness \(\max(1,10)+\max(10,100)=110\). Alternatively, she could swap the
first and second tiles so that \(a=[100,1,10]\), also achieving total ugliness
\(\max(100,1)+\max(1,10)=110\).
3 1
1 100 10
3110Bessie could swap the first and second tiles so that \(a=[100,1,10]\), achieving
total ugliness \(\max(100,1)+\max(1,10)=110\).
3 1
1 100 10
2200The initial total ugliness of the tiles is \(\max(1,100)+\max(100,10)=200\).
Bessie is only allowed to swap the first and third tiles, which does not allow
her to reduce the total ugliness.
4 2
1 3 2 4
2 39riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Platinum