Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

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

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Một bài nữa nè: Băng số   Sat 20 Mar 2010, 21:38

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.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 15:36

Ô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)
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 18:25

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.
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 18:32

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;
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 18:38

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.
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 19:23

có đọc mà ko hỉu.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 21 Mar 2010, 20:14

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.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Fri 14 May 2010, 19:38

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
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sat 15 May 2010, 13:13

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.
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 16 May 2010, 20:07

thua la sao hả cậu
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 16 May 2010, 20:22

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".
Về Đầu Trang Go down
toan_9a2
Gà con


Tổng số bài gửi : 17
Join date : 03/05/2010

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Sun 16 May 2010, 22:34

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..... Smile
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Mon 17 May 2010, 12:54

^^ . Đượ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.^^
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Mon 26 Jul 2010, 22:47

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.
Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Một bài nữa nè: Băng số   Today at 21:28

Về Đầu Trang Go down
 
Một bài nữa nè: Băng số
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến