USACO 2024 February Contest, Platinum, Minimum Sum of Maximums
Xem PDFBessie có \(N(2 \le N \le 300)\) miếng gạch trên một hàng với độ xấu lần lượt là \(a_1,a_2,…,a_N\), \((1 \le a_i \le 10^6)\). \(K(0 \le K \le min(N,6))\) miếng gạch ở các vị trí \(x_1,…,x_K \space (1\le x_1 < x_2...<x_K \le N)\) bị kẹt.
Bessie muốn tổng độ xấu của viên gạch có độ xấu lớn hơn trong 2 cặp viên gạch liên tiếp: \(\sum_{i=1}^{n-1} max(a_i,a_i+1)\) là nhỏ nhất. Cô ấy có thể thực hiện việc tráo đổi hai viên gạch không bị kẹt bất kì vô số lần.
Hãy tính tổng độ xấu nhỏ nhất có thể nếu Bessie thực việc tráo đổi một cách tối ưu.
Input
- Dòng đầu chứa hai số \(N\) và \(K\).
- Dòng tiếp theo chứa \(a_1,…,a_N\).
- Dòng cuối chứa \(K\) chỉ số \(x_1,…,x_K\).
Output
In ra tổng độ xấu nhỏ nhất có thể.
Scoring
- Subtask \(1\): \(K=0\)
- Subtask \(2\): \(K=1\)
- Subtask \(3\): \(N \le 50\)
- Subtask \(4\): Không có điều kiện gì thêm.
Example
Test 1
Input
3 0
1 100 10
Output
110
Note
Bessie có thể tráo đổi viên gạch thứ \(2\) và \(3\) và có \(a=[1,10,100]\), tổng độ xấu là \(max(1,10)+max(10,100)=110\). Hoặc cô ấy có thể tráo đổi viên gạch thứ \(1\) và \(2\) và có \(a=[100,1,10]\), cũng có tổng độ xấu là \(max(100,1)+max(1,10)=110\).
Test 2
Input
3 1
1 100 10
3
Output
110
Note
Bessie có thể tráo đổi viên gạch thứ \(2\) và \(1\) và có \(a=[100,1,10]\), tổng độ xấu là \(max(100,1)+max(1,10)=110\).
Test 3
Input
3 1
1 100 10
2
Output
200
Note
Tổng độ xấu ban đầu là \(max(1,100)+max(100,10)=200\). Bessie chỉ có thể tráo đổi viên gạch thứ \(3\) và \(1\), và không thể giảm độ xấu thấp hơn.
Test 4
Input
4 2
1 3 2 4
2 3
Output
9
Bình luận