LINEGAME – SPOJ

Đề bài: http://vn.spoj.com/problems/LINEGAME/

Thuật toán:

Đây là một bài quy hoạch động khá hay. Trước hết ta có thể ăn được 60% số Test bằng duyệt, hoặc Quy hoạch động với độ phức tạp O(n²), thậm chí làm Quy hoạch động với độ phức tạp O(n) mà dùng hai mảng một chiều 10⁶ phần tử chúng ta cũng chỉ đạt 60% số test.

Tôi xin trình bày ngắn gọn công thức sau với độ phức tạp O(n).

Gọi F[i,1] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘+’, tương tự F[i,2] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘-’ ta thấy:

F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1]).

F[i,2]=Max(F[i-1,1]-a[i],F[i-1,2]).

Với công thức trên chương trình có thể chạy với n=10⁶ trong 1s là cùng, nhưng đối với Time Limit nhỏ hơn như 0.5s thì rất dễ quá thời gian một cách đáng tiếc.

Ta để ý như sau: Tính F[i,1] và F[i,2] chỉ phụ thuộc vào F[i-1,1] và F[i-1,2] như vậy ta có thể dùng 3 biến m1,m2,m3 với vai trò như sau: m1 lưu F[i-1,1], m2 lưu F[i-1,2], m3 là trung gian và sau khi tính xong F[i,1] và F[i,2] thì m1,m2 lại được ghi đè lên giá trị của m1 và m2 lúc trước. Trong quá trình tính ta luôn cập nhật m1 và m2 với Max.

Trong chương trình chính ta tính luôn m1,m2 song song với đọc mảng a. Nói chung chương trình dưới đây chỉ sử dụng 7 biến kiểu nguyên và 1 biến tệp. Rất tiết kiệm bộ nhớ và CT ngắn gọn.

Độ phức tạp của thuật toán: O(n)
Code:

Const
        fi='';
        fo='';

Var
        n,a,i   :longint;
        m1,m2,m3:int64;
        max     :int64;
        f       :text;
Begin
        assign(f,fi);
        reset(f);
        max:=0;m1:=0;m2:=0;
        readln(f,n);
        for i:=1 to n do
                begin
                        read(f,a);{Doc a[i]}
                        m3:=m1;{Giu lai F[i-1,1] de tinh m2}
                        if m1max then max:=m1;{Cap nhat F[i,1] voi Max}
                        if m2>max then max:=m2;{Cap nhat F[i,2] voi Max}
                end;
        close(f);
        assign(f,fo);
	      rewrite(f);
        write(f,max);
        close(f);
End.