DHEXP spoj – Biểu thức

Nguồn đề bài: http://vn.spoj.com/problems/DHEXP/

1. Đề thi duyên hải môn tin học khối 10 2015

Một dãy gồm n số nguyên không âm a1, a2,…, an được viết thành một hàng ngang, giữa hai số liên tiếp có một khoảng trắng, như vậy có tất cả (-1) khoảng trắng. Người ta muốn đặt k dấu cộng và (n-1-k) dấu trừ vào (-1) khoảng trắng đó để nhận được một biểu thức có giá trị lớn nhất.

Ví dụ, với dãy gồm 5 số nguyên 28, 9, 5, 1, 69 và k = 2 thì cách đặt 28+9-5-1+69 là biểu thức có giá trị lớn nhất.

Yêu cầu: Cho dãy gồm n số nguyên không âm a1, a2,…, an và số nguyên dương k, hãy tìm cách đặt kdấu cộng và (n-1-k) dấu trừ vào (-1) khoảng trắng để nhận được một biểu thức có giá trị lớn nhất.

Input

–          Dòng đầu chứa hai số nguyên dương n, k (k < n);

–          Dòng thứ hai chứa n số nguyên không âm a1, a2,…, an (an ≤ 106)

Output

Một số nguyên là giá trị của biểu thức đạt được.

Example

Input:
5 2
28 9 5 1 69
Output:
100
 
Ghi chú:

  • Có 50% số test ứng với 50% số điểm có n ≤ 105k = 1;
  • Có 50% số test còn lại ứng với 50% số điểm có n ≤ 105;

2. Hướng dẫn DHEXP spoj

– Gợi ý dùng thuật toán tham lam, điền các dấu cộng vào k số lớn nhất. các số còn lại là dấu trừ.

Hướng dẫn cách làm

các bạn có thể dùng Quicksort để sắp xếp. sau đó chọn ra k số để đặt dấu trừ. lưu ý là không đặt dấu cho số đầu tiên.

3. Code tham khảo DHEXP spoj

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *