DHEXP spoj - Biểu thức - Kiến Thức 24h

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 a₁, a₂,…, a_n đượ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ả (n-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 (n-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 a₁, a₂,…, a_n 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 (n-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 a₁, a₂,…, a_n(a_n≤ 10⁶)

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 ≤ 10⁵ và k = 1;
Có 50% số test còn lại ứng với 50% số điểm có n ≤ 10⁵;

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

const   fi='';
        nmax=100000;
type    data=longint;
var
        f:text;
        A,id:array[0..nmax+1] of data;
        n,k:data;
        res:int64;

procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        readln(f,n,k);
        res:=0;
        for i:=1 to n do
                begin
                        read(f,a[i]);
                        id[i]:=i;
                        res:=res+a[i];
                end;
        close(f);
end;

procedure swap(var a,b:data);
var     z:data;
begin
        z:=a;
        a:=b;
        b:=z;
end;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do inc(i);
           while x<a[j] do dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                swap(id[i],id[j]);
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure xuli;
var     i,j:data;
begin
        sort(1,n);
        k:=n-1-k;
        for i:=1 to n do
                if id[i]<>1 then
                        begin
                                if k=0 then break;
                                res:=res-2*a[i];
                                dec(k);
                                if k=0 then break;
                        end;
        writeln(res);
end;

begin
        docfile;
        xuli;
end.

DHEXP spoj – Biểu thức