Thuật toán quan hệ động, chia để trị
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (72.31 KB, 2 trang )
Bài toán: Cho mảng a[1..n]. Mảng a[p..q] được gọi là một mảng con của a. Trọng
lượng mảng bằng tổng các phần tử của mảng. Tìm mảng con có trọng lượng lớn nhất
(1<=p<=q<=n).
Với bài toán này mình biết một cách làm là sử dụng kĩ thuật chia để trị, nhưng mình
không biết cách lưu giữa chỉ số của mảng con lớn nhất đó.
Chia: chia mảng a thành 2 mảng với độ chênh lệch ít nhất
Trị: gọi aL, aR lần lượt là mảng con có trọng số lớn nhất trong 2 mảng vừa chia ra.
Tổng hợp: mảng con lớn nhất cần tìm có thể là nằm trọn vẹn trong aL, hoặc aR, hoặc
chứa 2 điểm chia
Như vậy, ta có chương trình viết bằng ngôn ngữ tựa Pascal như sau:
function MaxSub(a: mảng; i, j: integer)
begin
if i = j then return a[i]
else
begin
m:= (i + j) div 2;
wL:= MaxSub(a, i, m);
wR:= MaxSub(a, m + 1, j);
wM:= MaxRight(a, i, m) + MaxLelf(a, m + 1, j);
return max(wL, wR, wM);
end;
end;
trong đó :
function MaxLelf(a: mảng; i, j: integer)
begin
max1:= - maxint;
s:= 0;
for k:= j downto i do
begin
s:= s + a[k];
if s > max1 then max1:= s;
end;
return max1;
end;
function MaxRight(a: mảng; i, j: integer)
begin
max1:= - maxint;
s:= 0;
for k:= i to j do
begin
s:= s + a[k];
if s > max1 then max1:= s;
end;
return max1;
end;
Bạn nào có thể giúp mình lưu trữ chỉ số để in ra mảng con lớn nhất đó không. Và
hình như bài này có thể sử dụng qui hoạch động nữa thì phải.
• Với đề bài như trên thì đây là 1 bài quy hoạch động khá cơ bản:
gọi S[i] là tổng các số của dãy từ 1 đến i -> tổng các số từ j đến i là S[i]-S[j-
1]
min[i]: min(S[1],S[2],...,S[i])
như thế thì giá trị lớn nhất của các dãy có phần tử cuối là i là S[i]-min[i-1]
Tóm lại là sau khi tính S[i] và min[i] thì với mỗi i ta tính S[i]-min[i-1], nếu giá
trị này lớn hơn giá trị lớn nhất đã tìm được thì lưu lại
Bài tương tự:
Đoạn con có tổng lớn nhất
Mã bài: GSS
Cho dãy số a[1], a[2], ..., a[n] (|a[i]| <= 15000, n <= 50000).
Hàm q(x, y) = max { tổng(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }.
Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x,
y).
Bài này test khá lớn nên các bạn muốn download test đành kích vào Edit problem ở
trên để download vậy.
Input
- Dòng đầu là n.
- Dòng thứ hai là dãy a.
- Dòng thứ 3 là m.
- m dòng tiếp theo mỗi dòng là 1 cặp số x, y.
Output
-> Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.
Example
Input:
3
-1 2 3
1
1 2
Output:
2
•
