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(n2), 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 106 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=106 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 m1<m2+a then m1:=m2+a;{m1=F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1])}
                        if m2<m3-a then m2:=m3-a;{m2=F[i,2]=Max(F[i-1,1]+a[i],F[i-1,2])}
                        if m1>max 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.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Comments

  1. sao bạn đã khai báo mảng đâu

  2. vs m là cái cj

Speak Your Mind

*