VOJ - SMARTDOG
Source: SMARTDOG
Tags: Dynamic Programming, Data Structures
Problems:
Bạn là một con chó, bạn thông minh và tham ăn. Bạn chơi một trò chơi qua N lượt, tại mỗi lượt bạn sẽ muốn quyết định rằng có đi đến vị trí (x[i], y[i]) để ăn bánh hay không, nếu không, bạn phải đứng yên tại chỗ và mất bánh, nếu muốn ăn bánh, bạn cần di chuyển mỗi bước là một đoạn song song với các trục tọa độ và có độ dài là 1, bạn sẽ được ăn c[i] cái bánh tại vị trí đó, tuy nhiên bạn lại không thể tới đó nếu số bước lớn hơn K (vì thế là không kịp). Ban đầu bạn đứng ở vị trí (0, 0) và bạn muốn ăn nhiều bánh nhất, vậy số bánh lớn nhất bạn có thể ăn được là bao nhiêu?
N ≤ 1e5. Các số còn lại trong bộ dữ liệu đều nguyên dương và ≤ 1e3.
Ví dụ:
Input:
8 4
1 2 2
1 5 9
4 3 3
6 4 4
7 7 8
8 2 5
5 1 6
3 2 7
Output:
27
Explanation:
Solution:
Ta có thể có một công thức DP đơn giản như thế này:
dp[i] = c[i] + dp[j] với i < j và |x[i] - x[j]| + |y[i] - y[j]| ≤ K.
Kết quả là dp[0] vì ta cần phải bắt đầu tại vị trí 0 có tọa độ là (0, 0).
Nhưng công thức DP này sẽ tốn rất nhiều thời gian và không phù hợp với giới hạn của N. Vậy ta sẽ phải tìm cách cải tiến.
Một vùng chứa những điểm mà từ (x[i], y[i]) có thể đi tới thực chất là một hình thoi giới hạn bởi 4 tọa độ là (x[i] - K, y[i]), (x[i], y[i] - K), (x[i] + K, y[i]) và (x[i], y[i] + K). Xoay hình lại ta có thể thấy rằng đây thực ra còn là một hình vuông và được giới hạn bởi các đường chéo chính phụ có giá trị như sau: x[i] - y[i] - K, x[i] - y[i] + K, x[i] + y[i] - K và x[i] + y[i] + K. Từ đây ta lập cây IT 2D để lưu các giá trị trong mảng quy hoạch động.
Độ phức tạp: O(Nlog^2(2000)) = khoảng O(100N)
Code: (Lưu ý là tọa độ các đường chéo chính phụ có thể âm, do đó lúc tìm vị trí giữa bằng công thức mid = (l + r) / 2 sẽ sai, do đó ta cần sửa công thức mid = l + (r - l + 1) / 2 - 1)
uses math;
var n, k, i, a, b: longint;
x, y, c: array [1..100000] of longint;
IT: array [1..8000, 1..8000] of longint;
function get(x1, y1, x2, y2: longint): longint;
function getB(i, k, l, r: longint): longint;
var m: longint;
begin
if (y2 < l) or (r < x2) then exit(0);
if (x2 <= l) and (r <= y2) then exit(IT[i][k]);
m := l + (r - l + 1) div 2 - 1;
exit(max(getB(i, 2 * k, l, m), getB(i, 2 * k + 1, m + 1, r)))
end;
function getA(k, l, r: longint): longint;
var m: longint;
begin
if (y1 < l) or (r < x1) then exit(0);
if (x1 <= l) and (r <= y1) then exit(getB(k, 1, 0, 2000));
m := l + (r - l + 1) div 2 - 1;
exit(max(getA(2 * k, l, m), getA(2 * k + 1, m + 1, r)))
end;
begin exit(getA(1, -1000, 1000)) end;
procedure update(x, y, v: longint);
procedure updateB(i, k, l, r: longint);
var m: longint;
begin
if (y < l) or (r < y) then exit;
IT[i][k] := max(IT[i][k], v);
if l < r then
begin
m := l + (r - l + 1) div 2 - 1;
updateB(i, 2 * k, l, m);
updateB(i, 2 * k + 1, m + 1, r)
end
end;
procedure updateA(k, l, r: longint);
var m: longint;
begin
if (x < l) or (r < x) then exit;
updateB(k, 1, 0, 2000);
if l < r then
begin
m := l + (r - l + 1) div 2 - 1;
updateA(2 * k, l, m);
updateA(2 * k + 1, m + 1, r)
end
end;
begin updateA(1, -1000, 1000) end;
begin
read(n, k);
for i := 1 to n do
read(x[i], y[i], c[i]);
for i := n downto 1 do
begin
a := x[i] - y[i]; b := x[i] + y[i];
update(a, b, get(a - k, a + k, b - k, b + k) + c[i])
end;
write(get(-k, k, -k, k))
end.
N ≤ 1e5. Các số còn lại trong bộ dữ liệu đều nguyên dương và ≤ 1e3.
Ví dụ:
Input:
8 4
1 2 2
1 5 9
4 3 3
6 4 4
7 7 8
8 2 5
5 1 6
3 2 7
Output:
27
Explanation:
Ta có thể có một công thức DP đơn giản như thế này:
dp[i] = c[i] + dp[j] với i < j và |x[i] - x[j]| + |y[i] - y[j]| ≤ K.
Kết quả là dp[0] vì ta cần phải bắt đầu tại vị trí 0 có tọa độ là (0, 0).
Nhưng công thức DP này sẽ tốn rất nhiều thời gian và không phù hợp với giới hạn của N. Vậy ta sẽ phải tìm cách cải tiến.
Một vùng chứa những điểm mà từ (x[i], y[i]) có thể đi tới thực chất là một hình thoi giới hạn bởi 4 tọa độ là (x[i] - K, y[i]), (x[i], y[i] - K), (x[i] + K, y[i]) và (x[i], y[i] + K). Xoay hình lại ta có thể thấy rằng đây thực ra còn là một hình vuông và được giới hạn bởi các đường chéo chính phụ có giá trị như sau: x[i] - y[i] - K, x[i] - y[i] + K, x[i] + y[i] - K và x[i] + y[i] + K. Từ đây ta lập cây IT 2D để lưu các giá trị trong mảng quy hoạch động.
Độ phức tạp: O(Nlog^2(2000)) = khoảng O(100N)
Code: (Lưu ý là tọa độ các đường chéo chính phụ có thể âm, do đó lúc tìm vị trí giữa bằng công thức mid = (l + r) / 2 sẽ sai, do đó ta cần sửa công thức mid = l + (r - l + 1) / 2 - 1)
uses math;
var n, k, i, a, b: longint;
x, y, c: array [1..100000] of longint;
IT: array [1..8000, 1..8000] of longint;
function get(x1, y1, x2, y2: longint): longint;
function getB(i, k, l, r: longint): longint;
var m: longint;
begin
if (y2 < l) or (r < x2) then exit(0);
if (x2 <= l) and (r <= y2) then exit(IT[i][k]);
m := l + (r - l + 1) div 2 - 1;
exit(max(getB(i, 2 * k, l, m), getB(i, 2 * k + 1, m + 1, r)))
end;
function getA(k, l, r: longint): longint;
var m: longint;
begin
if (y1 < l) or (r < x1) then exit(0);
if (x1 <= l) and (r <= y1) then exit(getB(k, 1, 0, 2000));
m := l + (r - l + 1) div 2 - 1;
exit(max(getA(2 * k, l, m), getA(2 * k + 1, m + 1, r)))
end;
begin exit(getA(1, -1000, 1000)) end;
procedure update(x, y, v: longint);
procedure updateB(i, k, l, r: longint);
var m: longint;
begin
if (y < l) or (r < y) then exit;
IT[i][k] := max(IT[i][k], v);
if l < r then
begin
m := l + (r - l + 1) div 2 - 1;
updateB(i, 2 * k, l, m);
updateB(i, 2 * k + 1, m + 1, r)
end
end;
procedure updateA(k, l, r: longint);
var m: longint;
begin
if (x < l) or (r < x) then exit;
updateB(k, 1, 0, 2000);
if l < r then
begin
m := l + (r - l + 1) div 2 - 1;
updateA(2 * k, l, m);
updateA(2 * k + 1, m + 1, r)
end
end;
begin updateA(1, -1000, 1000) end;
begin
read(n, k);
for i := 1 to n do
read(x[i], y[i], c[i]);
for i := n downto 1 do
begin
a := x[i] - y[i]; b := x[i] + y[i];
update(a, b, get(a - k, a + k, b - k, b + k) + c[i])
end;
write(get(-k, k, -k, k))
end.
Nhận xét
Đăng nhận xét