LINEGAME spoj – VOI09 Trò chơi với băng số

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

1. Đề bài LINEGAME spoj

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương a_i, i = 1, 2, …, n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i₁, i₂, …, i_k. Khi đó điểm số mà người chơi đạt được sẽ là:

• a_i1 – a_i2 + … + (-1)^k-1a_ik

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương n ( n ≤ 10⁶ ) là số lượng ô của băng số;
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n ( a_i ≤ 10⁴, i = 1, 2, …, n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả

• Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Ví dụ

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.

==============================

bài này sử dụng QHĐ:

2. code tham khảo LINEGAME spoj pascal , c++:

uses 	math;
const   fi='';
        nmax=1000000;
type    data=longint;
var
        n:data;
        a:array[1..nmax] of word;
        cong,tru:array[1..nmax] of int64;
        f:text;

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

procedure bpa;
var     i:data;
begin
        cong[1]:=a[1];
        tru[1]:=0;
        for i:=2 to n do
                begin
			cong[i]:=max(tru[i-1]+a[i],cong[i-1]);
			tru[i]:=max(cong[i-1]-a[i],tru[i-1]);
                end;
        writeln(max(cong[n],tru[n]));

end;


begin
        docfile;
        bpa;
        //readln;
end.

#include<cstdio>
using namespace std;

typedef long long int ll;

int main()
{
    int n,tg;
    ll max=0,m1=0,m2=0,m3;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&tg);
        m3=m1;
        if(m1<m2+tg) m1=m2+tg;
        if(m2<m3-tg) m2=m3-tg;
    }
    if(m1>max) max=m1;
    if(m2>max) max=m2;
    printf("%lld",max);
}