Minimum Sum of Maximums
다이아몬드 III의견: 0
Bessie has \(N\) (\(2\le N\le 300\)) tiles in a line with ugliness values
\(a_1, a_2, \dots, a_N\) in that order (\(1\le a_i\le 10^6\)). \(K\)
(\(0\le K\le \min(N,6)\)) of the tiles are stuck in place; specifically, those at
indices \(x_1,\dots, x_K\) (\(1\le x_1 < x_2<\dots< x_K\le N\)).
Bessie wants to minimize the total ugliness of the tiles, which is defined as
the sum of the maximum ugliness over every consecutive pair of tiles; that is,
\(\sum_{i=1}^{N-1}\max(a_i,a_{i+1})\). She is allowed to perform the following
operation any number of times: choose two tiles, neither of which are stuck in
place, and swap them.
Determine the minimum possible total ugliness Bessie can achieve if she performs
operations optimally.
Problem credits: Benjamin Qi
SCORING
- Input 5: \(K=0\)
- Inputs 6-7: \(K=1\)
- Inputs 8-12: \(N\le 50\)
- Inputs 13-24: No additional constraints
Problem credits: Benjamin Qi
The first line contains \(N\) and \(K\).
The next line contains \(a_1,\dots,a_N\).
The next line contains the \(K\) indices \(x_1,\dots,x_K\).
Output the minimum possible total ugliness.
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
평가 및 의견
Minimum Sum of Maximums
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Minimum Sum of Maximums