Bài tập Code backtracking, dp, training Dumv 13/11/2024 0 Comments

Fred And Bonus (public version)

Fred là học trò của thầy Ralf Rangnick. Sau khi thể hiện rất tốt trong trận đấu với câu lạc bộ Crystal Palace thì thầy Ralf Rangnick muốn thưởng cho Fred vì siêu phẩm mà anh đã ghi vào lưới của Crystal giúp mang về 3 điểm cho Manchester United. Cụ thể, thầy Ralf đưa ra n phần quà a₁, a₂, ..., a_n được xếp hàng từ trái qua phải. Nhưng thầy chỉ cho Fred chọn ra k cặp phần quà vì có 1 vài tình huống anh thể hiện chưa tốt. Fred sẽ không được chọn ngẫu nhiên mà phải chọn theo quy tắc sau:

Fred có thể thực hiện nhiều bước để chọn ra đúng k cặp phần quà, mỗi bước thực hiện 1 trong 5 quy tắc sau:

Fred chọn 2 phần quà đầu hàng.
Fred chọn 2 phần quà cuối hàng.
Fred chọn 1 phần quà đầu hàng và 1 phần quà cuối hàng.
Fred loại 1 phần quà đầu hàng ra khỏi hàng.
Fred loại 1 phần quà cuối hàng ra khỏi hàng.

Sau mỗi bước, nếu Fred chọn được 2 phần quà thì 2 phần quà đó được loại ra khỏi hàng và giá trị nhận phần thưởng được bằng trị tuyệt đối hiệu của 2 phần quà.

Với sự “đại đế” của mình, đương nhiên Fred muốn được nhiều phần thưởng nhất có thể. Nhưng do mới thi đấu xong nên Fred khá mệt để chọn phần quà 1 cách tối ưu. Bạn hãy giúp Đại Đế Fred thực hiện các bước chọn đúng k cặp phần quà để tổng giá trị phần thưởng là lớn nhất nhé.

Ví dụ:

n = 6, k = 2 và dãy a = [1, 3, 10, 2, 1, 4] thì chúng ta sẽ thực hiện cách chọn như sau:
- Bước 1: Chọn 2 phần quà cuối hàng và nhận được giá trị phần thưởng |4 - 1| = 3. Lúc này dãy phần quà còn a = [1, 3, 10, 2].
- Bước 2: Loại phần quà cuối cùng có giá trị 2 ra khỏi hàng. lúc này dãy phần quà còn a = [1, 3, 10].
- Bước 3: Chọn 1 phần quà đầu hàng và 1 phần quà cuối hàng và nhận được giá trị phần thưởng là |10 - 1| = 9 và dãy phần quà còn a = [3].
- Lúc này đã chọn được 2 cặp thẻ nên tổng giá trị phần thưởng là: 3 + 9 = 12. Đây là giá trị phần thưởng lớn nhất của dãy quà này.

[Đầu vào/Đầu ra]:

[Giới hạn thời gian]: 1s với C++, 6s với Java & C#, 8s với Python,Go,Js.
[Đầu vào]:
- Số tự nhiên n (1 ≤ n ≤ 400) biểu thị cho số phần quà mà thầy Ralf Rangnick đưa ra.
- Số tự nhiên k (2 * k ≤ n) biểu thị số cặp phần quà mà Fred được chọn.
- Array of integer a, vector biểu thị dãy n phần quà mà thầy Ralf Rangnick đưa ra. (0 ≤ a_i ≤ 10⁹), (0 ≤ i ≤ n - 1).
[Đầu ra]: Tổng giá trị phần quà lớn nhất có thể đạt được khi chọn đúng k cặp phần quà và chọn theo 5 quy tắc trên.