Một bài nữa nè: Băng số

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 ai, 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 ô i1, i2, ..., ik. Khi đó điểm số mà người chơi đạt được sẽ là:
• ai1 - ai2 + ... + (-1)k-1aik
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 ≤ 106 ) là số lượng ô của băng số;
• Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an ( ai ≤ 104, 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.

Ôi litlelee thể hiện một tham vọng. Đây là đề quốc gia 12 cơ mà.
Một đặc trưng của qui hoạch động 2 lớp với 1 vòng for.
Có thể nâng dữ liệu bài này lên 10^8 vẫn chạy dưới 1 giây (không tính thời gian đọc file nha)

administrators đã viết:

Ôi litlelee thể hiện một tham vọng. Đây là đề quốc gia 12 cơ mà.
Một đặc trưng của qui hoạch động 2 lớp với 1 vòng for.
Có thể nâng dữ liệu bài này lên 10^8 vẫn chạy dưới 1 giây (không tính thời gian đọc file nha)

Đúng là littlelee tham vọng thật. Vì dù sao đi nữa littlelee rất yêu môn lập trình này. Mặc dù chưa giải được bài này, tuy nhiên littlelee hi vọng sau khi được thảo luận thì có thể giải được bài này.

Tặng bạn nè.

Phân tích
- Gọi g[i] là dãy con theo qui luật trên có giá trị lớn nhất, phần tử cuối cùng là a[i] và mang dấu “–“
- Gọi f[i] là dãy con theo qui luật trên có giá trị lớn nhất, phần tử cuối cùng là a[i] và mang dấu “+“
- Với mọi i> 0 ta có:
* g[i] = max(f[j<i]) – a[i];
* f[i] = max(g[j<i]) + a[i];

Đoạn mã thể hiện thuật toán có độ phức tạp O(n).

g[0]:=0;
f[0]:=0;
gmax:=0;
fmax:=0;
For i:=1 to n do
Begin
G[i]:= fmax - a[i];
F[i]:= gmax + a[i];
If gmax<g[i] then gmax:=g[i];
If fmax< f[i] then fmax:= f[i];
End;
KQ -> fmax;

administrators đã viết:

Tặng bạn nè.

Phân tích
- Gọi g[i] là dãy con theo qui luật trên có giá trị lớn nhất, phần tử cuối cùng là a[i] và mang dấu “–“
- Gọi f[i] là dãy con theo qui luật trên có giá trị lớn nhất, phần tử cuối cùng là a[i] và mang dấu “+“
- Với mọi i> 0 ta có:
* g[i] = max(f[j<i]) – a[i];
* f[i] = max(g[j<i]) + a[i];

Đoạn mã thể hiện thuật toán có độ phức tạp O(n).

g[0]:=0;
f[0]:=0;
gmax:=0;
fmax:=0;
For i:=1 to n do
Begin
G[i]:= fmax - a[i];
F[i]:= gmax + a[i];
If gmax<g[i] then gmax:=g[i];
If fmax< f[i] then fmax:= f[i];
End;
KQ -> fmax;

Cảm ơn ad. Mình sẽ cố gắng hiểu được ý nghĩa đoạn này.

có đọc mà ko hỉu.

Hi hi, giống mình. Công nhận khá khó hiểu. À mà này, sao dạo này thấy ít lên vậy. Mới lên trả lời có một bài này đã thoát khỏi diễn đàn rồi.

cach de hieu ne:

var a,b,c,n,s,d:integer;
i:longint;
BEGIN
readln(n);
readln(a);
d:=a;
for i:=2 to n do
begin
readln(c);
if c>a then d:=d-a+c;
a:=c;
end;
writeln(d);
readln
en

Uhm, tất nhiên là cách này dễ hiểu, nhưng test thì cách này thua. Mà dù sao đi chăng nữa thì giờ mình đã hiểu cách Qhđ rồi.

thua la sao hả cậu

Thua cái này nè "Có thể nâng dữ liệu bài này lên 10^8 vẫn chạy dưới 1 giây".

thiệt hả..............sao lại zậy nhỉ....phần độ phức tạp của thuât toán tớ học không kỹ lắm.....

^^ . Được học thì điều đó cũng đã đáng tự hào rồi. Tụi tớ còn ko được học, chỉ tự hiểu thôi.

Không cần 10^8 đâu, chỉ cần 10^6 gặp test khó thì cách bình thường đã chạy cả tiếng rồi.^^

Code:

const nmax = 1000000;
var A:Array[1..nmax] of longint;
F,max:array[1..2,1..nmax] of int64;
N:longint;
procedure nhap;
var i:longint;
Begin
readln(N);
for i:=1 to N do
read(A[i]);
end;
function Max (x,y:int64):int64;
begin
if x > y then max := x
else max := y;
end;
procedure xuly;
var i:longint;
Begin
F[1,1] := A[1];
F[2,1] := 0;
max[1,1] := A[1];
max[2,1] := 0;
for i:=2 to N do
Begin
F[1,i] := max[2,i-1] + A[i];
F[2,i] := max[1,i-1] - A[i];
max[1,i] := max (F[1,i],max[1,i-1]);
max[2,i] := max (F[2,i],max[2,i-1]);
end;
end;
procedure ghi;
Begin
Writeln(F[1,N]));
end;
Begin
nhap;
xuly;
ghi;
end.