VOI 20 Bài 1 - Phần thưởng - VNOJ: VNOI Online Judge

VOI 20 Bài 1 - Phần thưởng

Điểm: 0,50 (OI)

Giới hạn thời gian: 0.45s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Kỳ thi Học sinh giỏi Quốc gia 2020 - Ngày 1

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đọc đề gốc tại đây.

Alice vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau. Có ~n~ thẻ xếp trên một hàng dài, trên mỗi thẻ viết một số nguyên dương. Ban tổ chức cho phép Alice thực hiện nhiều bước để chọn ra đúng ~k~ cặp thẻ, mỗi bước thực hiện theo một trong các quy tắc sau:

Chọn ~2~ thẻ đầu hàng;
Chọn ~2~ thẻ cuối hàng;
Chọn ~1~ thẻ đầu hàng và ~1~ thẻ cuối hàng;
Loại ~1~ thẻ đầu hàng ra khỏi hàng;
Loại ~1~ thẻ cuối hàng ra khỏi hàng.

Sau mỗi bước nếu chọn được ~2~ thẻ thì loại ~2~ thẻ đó ra khỏi hàng và Alice nhận được số tiền thưởng bằng giá trị tuyệt đối của hiệu hai số ghi trên hai thẻ đó.

Yêu cầu: Hãy giúp Alice tìm cách chơi chọn đúng ~k~ cặp thẻ để đạt được tổng số tiền thưởng là lớn nhất.

Input

Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~k~ ~(2 \times k \leq n)~;
Dòng thứ hai chứa ~n~ số nguyên dương là giá trị ghi trên từng thẻ, mỗi thẻ một số tương ứng lần lượt từ đầu hàng. Các số có giá trị không vượt quá ~10^9~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất tìm được.

Giới hạn

Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 300~, ~k \leq 2~;
~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 30~, ~2 \times k = n~;
~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 300~.

Sample Input

6 2
1 3 10 2 1 4

Sample Output

Note

Giải thích test ví dụ

Bước ~1~: Alice chọn hai thẻ cuối hàng là ~1~ và ~4~ và nhận được số tiền thưởng là ~|4 - 1| = 3~;
Bước ~2~: Alice loại thẻ cuối hàng có giá trị ~2~;
Bước ~3~: Alice chọn một thẻ đầu hàng và một thẻ cuối hàng là ~1~ và ~10~ và nhận được số tiền thưởng là ~|10 - 1| = 9~;

Tổng tiền thưởng Alice nhận được là ~3 + 9 = 12~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

-8

phuocle đã bình luận lúc 12, Tháng 12, 2025, 8:10

bai de vl, may con ga thi biet gi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

5
minhkochamhoc đã bình luận lúc 7, Tháng 12, 2025, 3:15 ← sửa 4 →
solve

sub1 : n <= 300 && k <= 2

vì k <= 2 nên chỉ có 2 trường hợp có thể xảy ra là k = 1 và k = 2 cho nên ta xét 2 trường hợp như sau :

TH 1 với k = 1 :

ta thấy rằng với k = 1 bài toán trở thành chọn cặp i , j sao cho abs(card[i] - card[j]) là lớn nhất vậy ta có thể sài cách duyệt O(~n^2~) xét từng cặp vì độ phức tạp O(~n^2~) qua thoải mái

TH 2 với k = 2 :

lúc này vì đã phải chọn 2 cặp nên ý tưởng đầu tiên của ta sẽ là nghĩ tới thuật O(~n^4~) bằng cách duyệt 4 con trỏ i,j,k,t

nhưng rõ ràng ta thấy nếu sài thuật O(~n^4~) ta sẽ bị TLE cho nên ta có thể đưa ra nhận xét như sau :

giả sử ta xét 4 vị trí i , j , k , t (i < j < k < t) thì ta sẽ có 3 cách ghép cặp là:

(i , j) và (k , t) : ghép liền kề theo vị trí

(i , k) và (j , t) : ghép chéo

(i , t) và (j , k) : cặp ngoài cặp trong

từ 3 cách ghép trên dễ thấy cách ghép chéo (i , k) và (j , t) là ko thể thực hiện được do đề chỉ cho phép ta lấy 2 vị kề nhau hoặc 2 vị trí đầu mút của 1 đoạn cho nên nếu lấy i,k thì ta đã phải xóa mất t do i < j < k < t thì phải xóa t mới đi tới ghép i và k được mà xóa t đồng nghĩa ko thể ghép (j , t)

vì vậy ta chỉ phải xét 2 trường hợp là chọn 2 cặp mà cặp nào cx là phần tử kề nhau hoặc chọn 2 cặp mà cả mỗi cặp được tạo nên từ việc lấy 2 phần tử đầu mút của mỗi đoạn .

chọn 2 cặp kề nhau : ta for lấy 2 vị trí i , j và xét kết quả 2 cặp (i ,i + 1) , (j , j + 1) chỉ cần nhớ kiểm tra sao cho j + 1 <= n là được , độ phức tạp O(~n^2~)

chọn 2 cặp lấy 2 vị trí đầu mút : ta thấy rằng khi xét kết quả của cặp i , t qua công thức abs(card[i] - card[t]) thì để kết quả là tốt nhất khi xét với i bất kỳ ta sẽ muốn card[t] phải là cực tiểu hoặc cực đại của đoạn đằng sau vì như vậy chênh lệch khi lấy trị tuyệt đối sẽ càng lớn vì vậy ta có thể gọi Maxlater[i] , Minlater[i] là cực đại hoặc cực tiểu đại được khi xét đoạn từ i -> n (2 mảng này có được bằng cách xây dựng ngược) . từ đây ta có thể giảm độ phức tạp từ ~n^4~ về ~n^3~ vì bình thường việc ghép i thì ta phải kiếm phần tử t ở đằng sau nhưng giờ thì ta có thể lấy kết quả Max hoặc Min của đoạn sau làm cái trường hợp tốt nhất từ đó ta chỉ cần for i , j , k để ghép (j , k) còn ghép (i , t) ta sẽ lấy t là 2 trường hợp cực đại hoặc cực tiểu từ k -> n bằng Maxlater[k+1] , Minlater[k+1] , độ phức tạp O(~n^3~)

vậy sub1 nếu k = 1 thì độ phức tạp O(~n^2~) , k = 2 thì O(~n^3~)

sub2 : n <= 30 && 2 * k = n

do 2 * k = n thì đồng nghĩa ta phải chọn hết toàn bộ mảng mà ko bỏ qua bất kì phần tử nào vì vậy hiệu ứng xóa phần tử đầu dãy hay cuối dãy bị vô hiệu hóa

vì vậy ở mỗi lượt ta chỉ có 3 hiệu ứng là chọn 2 phần tử đầu , chọn 2 phần tử cuối , chọn 1 đầu 1 cuối

đễ thấy với n = 30 -> k = 15 thì giả sử xét toàn bộ phương án chọn ta sẽ có độ phức tạp cỡ O(~3^k~) là 3^15 thì đây là 1 độ phức tạp nhỏ có thể qua được cho nên ta sẽ xây dựng hàm backtrack như sau

gọi backtrack(int LEFT , int RIGHT , int cnt , long long sum) là giá trị đạt được khi đang xét tới đoạn [LEFT , RIGHT] và trước đó đã chọn cnt cặp để có tổng là sum

nếu cnt = k thì ta lưu lại tổng lớn nhất rồi return xét nhánh khác

nếu cnt != k ta sẽ có thể gọi tiếp hàm backtrack như sau :

backtrack(LEFT + 1 , RIGHT - 1 , cnt + 1 , sum + abs(card[LEFT] - card[RIGHT]) )

backtrack(LEFT + 2 , RIGHT , cnt + 1 , sum + abs(card[lEFT] - card[LEFT + 1]) )

backtrack(LEFT , RIGHT - 2 , cnt + 1 , sum + abs(card[RIGHT] - card[RIGHT - 1]) )

độ phức tạp O(~3^k~)

sub3 : n <= 300 && k bất kỳ

giả sử khi đang xét đoạn [LEFT , RIGHT] mà muốn chọn cnt cặp thì có phải để tối ưu ta cần biết kết quả lớn nhất khi xét

[LEFT + 1 , RIGHT - 1] chọn cnt - 1 cặp

[LEFT + 2 , RIGHT] chọn cnt - 1 cặp (để lấy cặp đầu)

[LEFT , RIGHT - 2] chọn cnt - 1 cặp (để lấy cặp cuối)

[LEFT + 1 , RIGHT] chọn cnt cặp (xóa đầu vì có phương án tốt hơn ở sau)

[LEFT , RIGHT - 1] chọn cnt cặp (xóa cuối vì có phương án tốt hơn ở trước)

vì vậy ta thấy rằng bài toán có tính chất tái sử dụng kết quả con hay nói cách khác xây dựng kết quả lớn hơn bằng các kết quả nhỏ hơn trước đó cho nên ta khẳng định đây là dạng quy hoạch động và được giải bằng cách quy hoạch động trên đoạn do đoạn lớn hơn được xây từ kết quả đoạn nhỏ hơn

cho nên ta định nghĩa dp[LEFT][RIGHT][cnt] là tổng lớn nhất đạt được khi chọn cnt cặp từ đoạn [LEFT , RIGHT]

trường hợp cơ sở là các đoạn độ dài 2 vì lúc này ta chỉ cần chọn luôn 2 phần tử của đoạn đó chứ ko quan tâm cách chọn -> dp[i][i+1][1] = abs(card[i] - card[i+1])

ta xét dần từ các cnt con để làm kết quả cho cnt lớn , với mỗi cnt đang xét ta cũng xét các đoạn độ dài nhỏ tới lớn để xây kết quả cho cnt này vì vậy ta có công thức như sau

dp[LEFT][RIGHT][cnt] = max của 5 hiệu ứng :

dp[LEFT + 1][RIGHT - 1][cnt - 1] + abs(card[LEFT] - card[RIGHT])

dp[LEFT + 2][RIGHT][cnt - 1] + abs(card[LEFT] - card[LEFT + 1])

dp[LEFT][RIGHT - 2][cnt - 1] + abs(card[RIGHT] - card[RIGHT - 1])

dp[LEFT + 1][RIGHT][cnt]

dp[LEFT][RIGHT - 1][cnt]

kết quả cuối cùng là dp[1][n][k]

độ phức tạp O(~n^2~ * k)

đây là code của mình : VOI20

mình tin rằng cách giải của mình cho từng sub chưa phải là tốt nhất (nhất là sub1 với k = 2 mình trình bày , code chưa đc tốt) nhưng mong rằng nó có thể giúp đỡ đc cho mọi người hê hê hê