AMSSEQ spoj - Dãy số - Kiến Thức 24h

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

1. Đề bài AMSSEQ spoj

Cho 1 dãy số gồm N phần tử (N ≤ 10000), mỗi phần tử có 1 giá trị nằm trong khoảng [-1000, 1000]. Ban đầu, bạn sẽ ở vị trí ô số 0 với tổng điểm là 0. Mỗi nước đi, người chơi có thể di chuyển sang phải tối thiểu là 1 bước và tối đa là K bước (K ≤ 10) . Khi dừng lại ở 1 ô nào đó thì giá trị của ô đó sẽ được cộng vào tổng điểm. Bạn có thể dừng cuộc chơi bất cứ lúc nào. Hãy tìm cách chơi sao cho tổng điểm nhận được là nhiều nhất.

Dữ liệu vào

Dòng đầu tiên chứa 2 số N, K.

Dòng thứ 2 chứa N số của dãy, mỗi số cách nhau 1 dấu cách. Mỗi số nằm trong khoảng [-1000, 1000]

Dữ liệu ra

Số điểm lớn nhất có thể đạt được.

Giới hạn:

N ≤ 10000.
K ≤ 10.
Trong 20% số test có N ≤ 10

Ví dụ

Input:
5 2
-2 3 -6 -4 5

Output:
4

Giải thích:
– Ta có thể đi theo thứ tự 0 -> 2 -> 4 -> 5. Số điểm đạt được là 0 + 3 – 4 + 5 = 4.

2. Thuật Toán AMSSEQ spoj

– Sử dụng QHĐ.

– gọi F[i] là số điểm lớn nhất đạt được khi đến ô vị trí i.

– khởi tạo F[1]=max(0,a[1]);

– F[i]=max(F[i],F[i-j]+a[i]) với (i=2..n ; j=1..k)

Kết quả bài toán là Max(F[i]) với (i=1..n).

3. Code tham khảo AMSSEQ spoj

[sociallocker]

uses math;
const   fi='';
        nmax=10000;
type    data=longint;
var
        F,A:array[-50..nmax+1] of data;
        n,k:data;

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

procedure QHD;
var     i,j,res:data;
begin
        res:=0;
        fillchar(F,sizeof(f),0);
        f[1]:=max(0,a[1]);
        for i:=2 to n do
                begin
                        F[i]:=low(data);
                        for j:=1 to k do
                                F[i]:=max(F[i],F[i-j]+A[i]);
                        res:=max(res,f[i]);
                end;
        writeln(res);
end;

begin
        docfile;
        QHD;
end.

[/sociallocker]

AMSSEQ spoj – Dãy số