Frog 2 (AtCoder Educational DP Contest B)

Nguồn: AtCoder Educational DP Contest (VNOJ) Độ khó: Dễ Quy hoạch động QHĐ tuyến tính

Đề bài

Atcoder Educational DP Contest B – Frog 2

Có $N$ hòn đá, được đánh số từ $1$ đến $N$. Với mỗi chỉ số $i$ $(1 \le i \le N)$, độ cao của hòn đá thứ $i$ là $h_i$.

Ban đầu, có một chú ếch đang ngồi ở hòn đá thứ nhất và chú sẽ thực hiện liên tục một loạt các hành động sau:

• Nếu chú đang ngồi ở hòn đá $i$ chú có thể nhảy đến các hòn đá thứ $i + 1, i + 2, \ldots, i + K$. Chú sẽ mất phí khi nhảy là $|h_i - h_j|$ với $j$ là hòn đá mà chú ếch nhảy đến.

Bạn hãy giúp chú ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$ nhé.

Input:

• Dòng đầu tiên của dữ liệu vào chứa hai số nguyên dương $N$ và $K$ $(2 \le N \le 10^5,\ 1 \le K \le 100)$, lần lượt là số lượng hòn đá và giới hạn nhảy của ếch.
• Dòng thứ hai gồm $N$ số nguyên $h_i$ $(1 \le i \le N,\ 1 \le h_i \le 10^4)$, là độ cao của hòn đá thứ $i$.

Output: Gồm một số nguyên, là chi phí ít nhất để nhảy từ hòn đá thứ nhất đến hòn đá thứ $N$.

Sample 1 – input

5 3
10 30 40 50 20

Sample 1 – output

30

Một đường đi tối ưu là: $1 \to 2 \to 5$. Chi phí sẽ là $|10 - 30| + |30 - 20| = 30$.

Sample 2 – input

3 1
10 20 10

Sample 2 – output

20

Một đường đi tối ưu là: $1 \to 2 \to 3$. Chi phí sẽ là $|10 - 20| + |20 - 10| = 20$.

Sample 3 – input

2 100
10 10

Sample 3 – output

0

Một đường đi tối ưu là: $1 \to 2$. Chi phí sẽ là $|10 - 10| = 0$.

Sample 4 – input

10 4
40 10 20 70 80 10 20 70 80 60

Sample 4 – output

40

Một đường đi tối ưu là: $1 \to 4 \to 8 \to 10$. Chi phí sẽ là $|40 - 70| + |70 - 70| + |70 - 60| = 40$.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Đây là bài B trong bộ Educational DP Contest nổi tiếng của AtCoder – bản "nâng cấp" của bài Frog 1: thay vì chỉ nhảy 1 hoặc 2 bước, giờ chú ếch được nhảy tối đa $K$ bước.

Mình giải thích ví dụ mẫu 1 để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $N = 5$ hòn đá cao lần lượt $10, 30, 40, 50, 20$, mỗi lần ếch nhảy được $1$, $2$ hoặc $3$ hòn ($K = 3$). Một vài cách đi:

• $1 \to 2 \to 3 \to 4 \to 5$: $20 + 10 + 10 + 30 = 70$.
• $1 \to 4 \to 5$: $|10 - 50| + |50 - 20| = 40 + 30 = 70$.
• $1 \to 3 \to 5$: $|10 - 40| + |40 - 20| = 30 + 20 = 50$.
• $1 \to 2 \to 5$: $|10 - 30| + |30 - 20| = 20 + 10 = 30$ – đây là ít nhất, đáp án là 30.

Lưu ý từ hòn $1$ không nhảy thẳng tới hòn $5$ được vì $5 - 1 = 4 \gt K = 3$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Đệ quy thử mọi đường · hàm mũ · TLECách 2Quy hoạch động 4 bước · O(N·K) · AC

Cách 1Đệ quy thử mọi đường đi – hàm mũ

Trước khi vào lời giải chính, mình thử cách "làm theo đề" để các bạn thấy vì sao cần quy hoạch động. Gọi solve(i) là chi phí ít nhất để đi từ hòn $i$ tới hòn $N$. Đứng ở hòn $i$ thì ếch thử nhảy tới từng hòn $j = i+1, \ldots, \min(N, i+K)$, mất phí $|h_i - h_j|$ rồi đi tiếp từ $j$: solve(i) = min(|h[i] - h[j]| + solve(j)), và solve(N) = 0. Đáp án là solve(1).

Cách này đúng, nhưng có một vấn đề rất lớn: solve(j) của cùng một $j$ bị gọi đi gọi lại rất nhiều lần (ví dụ solve(4) được gọi từ cả solve(1), solve(2), solve(3)…), mỗi lần lại tính lại từ đầu. Số lời gọi tăng theo hàm mũ của $N$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[100005];

int solve(int i){
    if(i == n){
        return 0;
    }
    int best = INT_MAX;
    for(int j = i + 1; j <= min(n, i + k); ++j){
        best = min(best, abs(a[i] - a[j]) + solve(j));
    }
    return best;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    cout << solve(1);
    return 0;
}

import sys
sys.setrecursionlimit(10000)
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(v) for v in data[2:2 + n]]

def solve(i):
    if i == n:
        return 0
    best = float('inf')
    for j in range(i + 1, min(n, i + k) + 1):
        best = min(best, abs(a[i] - a[j]) + solve(j))
    return best

print(solve(1))

C++▶ Chạy tay từng dòng codeCách 1: solve(i) thử nhảy tới từng j = i+1..min(n, i+k), lấy min |a[i]-a[j]| + solve(j).

Dữ liệu vào (stdin) – sửa thoải mái5 3 10 30 40 50 20

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int n, k;

5int a[100005];

6

7int solve(int i){

8 if(i == n){

9 return 0;

10 }

11 int best = INT_MAX;

12 for(int j = i + 1; j <= min(n, i + k); ++j){

13 best = min(best, abs(a[i] - a[j]) + solve(j));

14 }

15 return best;

16}

17

18int main(){

19 ios::sync_with_stdio(0);

20 cin.tie(0);

21 cin >> n >> k;

22 for(int i = 1; i <= n; ++i){

23 cin >> a[i];

24 }

25 cout << solve(1);

26 return 0;

27}

ChậmVừaNhanhRất nhanh

Các bạn bấm nút Gọi lặp lại nhiều rồi bấm ⏭ để xem: chỉ với $n = 6$, $k = 3$ mà solve(6) đã bị gọi tới 13 lần.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng độ cao và độ sâu đệ quy.
• Thời gian: số lời gọi tăng theo hàm mũ của $N$, không thể chạy với $N = 10^5$.

Không gian$O(N)$

Thời gianhàm mũ

TLE chắc chắn

Mình đo thử bản C++: với $N = 30$, $K = 3$ đã mất gần 1 giây; với $N = 40$, $K = 40$ thì chạy quá 10 giây vẫn chưa xong. Trong khi đề cho $N$ tới $10^5$. Mấu chốt để sửa: mỗi bài toán con chỉ nên tính đúng 1 lần rồi lưu lại – đó chính là quy hoạch động.

Cách 2Quy hoạch động 4 bước – O(N·K)

Bài này áp dụng phương pháp Quy Hoạch Động (Dynamic Programming) để giải quyết nhé các bạn. Cho bạn nào đã biết cơ bản qua về quy hoạch động rồi thì 4 bước giải một bài toán quy hoạch động như sau.

1Bài toán con: $F[i]$ là năng lượng nhỏ nhất để ếch đi từ cột $1$ đến cột $i$.

2Bài toán cơ sở: $F[1] = 0$.

3Đáp án: $F[N]$.

4Truy hồi: $F[i] = \min\limits_{\max(1,\,i-K) \le j \lt i} \big(F[j] + |h_i - h_j|\big)$.

(Thầy gọi hòn đá là "cột" và chi phí là "mức năng lượng" cho dễ hình dung nha các bạn.)

Bước 1: Xác định bài toán con

Gọi $F[i]$ là mức năng lượng nhỏ nhất của con ếch khi đi từ cột $1$ đến cột $i$.

Bước 2: Xác định bài toán cơ sở

$F[1] = 0$, bởi vì ban đầu con ếch đã ở sẵn cột $1$ rồi nên nó không cần mất năng lượng gì khi di chuyển từ cột $1$ đến cột $1$ cả.

Bước 3: Xác định đáp án bài toán

Quá rõ ràng đó chính là $F[N]$, vì đề bài đang yêu cầu tìm mức năng lượng nhỏ nhất để con ếch đi từ cột $1$ đến cột $N$.

Bước 4: Xác định công thức truy hồi

Nếu muốn đi đến vị trí $i$ thì trước đó con ếch phải ở một trong các vị trí $i - 1$, $i - 2$, $i - 3$, …, $i - K$: xa nhất là $i - K$ để với một bước nhảy $1$ hay $2$ hay … hay $K$ ô thì con ếch đến được vị trí $i$.

Để năng lượng là nhỏ nhất, ta thử từng vị trí đứng trước đó: năng lượng khi đứng ở vị trí $j$ (cũng đã là nhỏ nhất tính từ đầu đến $j$, tức $F[j]$), cộng thêm năng lượng để từ $j$ nhảy tiếp đến $i$ là $|h_i - h_j|$. Trong tối đa $K$ vị trí đó, vị trí nào cho tổng nhỏ nhất thì $F[i]$ lấy theo:

$F[i] = \min\big(F[i-1] + |h_i - h_{i-1}|,\ F[i-2] + |h_i - h_{i-2}|,\ \ldots,\ F[i-K] + |h_i - h_{i-K}|\big)$

Công thức truy hồi

$F[i] = \min\limits_{\max(1,\, i-K) \le j \lt i} \big(F[j] + |h_i - h_j|\big)$,  $F[1] = 0$,  đáp án $F[N]$.

Vị trí nhỏ nhất là 1

Tối đa chỉ lấy $K$ vị trí trước đó; nếu không đủ $K$ thì vị trí lấy cuối cùng dừng lại ở $1$ (vị trí xuất phát của con ếch). Ví dụ $K = 4$ và đang xét $i = 7$ thì ta xét 4 vị trí đứng trước là $3, 4, 5, 6$. Nhưng nếu $i = 3$ thì chỉ xét $1, 2$ thôi, chứ không có chuyện xét các vị trí $-1$, $0$ nha các bạn. Đó là lý do trong code có max(1, i - k).

Với sample 1 ($K = 3$, $h = 10, 30, 40, 50, 20$): $F[1] = 0$; $F[2] = 0 + 20 = 20$; $F[3] = \min(20 + 10,\ 0 + 30) = 30$; $F[4] = \min(30 + 10,\ 20 + 20,\ 0 + 40) = 40$; $F[5] = \min(40 + 30,\ 30 + 20,\ 20 + 10) = 30$ ✅ (đi từ hòn 2).

Minh hoạ: ếch tới hòn i từ đâu là rẻ nhất?

Các bạn nhập $K$ và dãy độ cao rồi bấm Tiếp. Với mỗi hòn $i$, các mũi tên là những cú nhảy có thể tới $i$ (từ $K$ hòn trước), mũi tên xanh là cú nhảy cho $F[i]$ nhỏ nhất. Bước cuối sẽ tô lại đường đi tối ưu:

K Độ cao h

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    int a[n + 1];
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    int f[n + 1];
    f[1] = 0;
    for(int i = 2; i <= n; ++i){
        f[i] = f[i - 1] + abs(a[i - 1] - a[i]);
        int finish = max(1, i - k);
        for(int j = i - 2; j >= finish; --j){
            f[i] = min(f[i], f[j] + abs(a[j] - a[i]));
        }
    }
    cout << f[n];
    return 0;
}

import sys
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = int(data[1 + i])
f = [0] * (n + 1)
f[1] = 0
for i in range(2, n + 1):
    f[i] = f[i - 1] + abs(a[i - 1] - a[i])
    finish = max(1, i - k)
    for j in range(i - 2, finish - 1, -1):
        f[i] = min(f[i], f[j] + abs(a[j] - a[i]))
print(f[n])

C++▶ Chạy tay từng dòng codeCách 2: f[i] mặc định nhảy từ i-1, rồi so với các j = i-2 xuống tới max(1, i-k).

Dữ liệu vào (stdin) – sửa thoải mái5 3 10 30 40 50 20

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n, k;

8 cin >> n >> k;

9 int a[n + 1];

10 for(int i = 1; i <= n; ++i){

11 cin >> a[i];

12 }

13 int f[n + 1];

14 f[1] = 0;

15 for(int i = 2; i <= n; ++i){

16 f[i] = f[i - 1] + abs(a[i - 1] - a[i]);

17 int finish = max(1, i - k);

18 for(int j = i - 2; j >= finish; --j){

19 f[i] = min(f[i], f[j] + abs(a[j] - a[i]));

20 }

21 }

22 cout << f[n];

23 return 0;

24}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong cách làm ở trên:

1. 2 dòng đầu của hàm main (ios::sync_with_stdio(0); cin.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (để hiểu vì sao thì cứ gõ mấy từ này lên Google là ra rất nhiều bài viết giải thích nhé). Bài này $N$ có thể tới $10^5$, tức là cả 100,000 phần tử cần nhập, nên hãy thêm 2 dòng này vào cho chạy nhanh hơn.
2. Do bài này vị trí tính từ $1$, để thống nhất tránh rắc rối không cần thiết ta khởi tạo mảng có $n + 1$ phần tử để chỉ số chạy từ $0$ đến $n$, coi như bỏ qua không xài chỉ số $0$, chỉ xài từ $1$ đến $n$.
3. Khởi tạo f[1] = 0 chính là bước 2 (bài toán cơ sở). Rồi xét $i$ từ $2$ đến $n$. Vì tối thiểu $K$ cũng là $1$ nên f[i] gán luôn mặc định là f[i - 1] + abs(a[i - 1] - a[i]): năng lượng nhỏ nhất để đến cột $i - 1$, cộng năng lượng để nhảy từ cột $i - 1$ sang cột $i$ – tức là năng lượng nhỏ nhất đến cột $i$ nếu vị trí đứng trước đó là $i - 1$. Sau đó ta xét tiếp các vị trí đứng trước hợp lệ còn lại (từ $i - 2$ lùi về finish), so sánh và cập nhật nếu tìm ra giá trị nhỏ hơn, để sau cùng f[i] mang giá trị nhỏ nhất. Lặp đủ $i$ đến $n$ là có f[n] – đáp án cần tìm.
4. Kiểu int là đủ: mỗi bước nhảy tốn tối đa $10^4 - 1$, đi qua tối đa $10^5 - 1$ bước nên $F[N] \lt 10^9$, chưa chạm giới hạn của int.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(2 \cdot N)$ cho 2 mảng $a$, $f$, tức là $O(N)$, với $N$ là số lượng cột.
• Thời gian: $O(N)$ của bước đọc dữ liệu cộng $O(N \cdot K)$ của bước xử lý ($N$ là số cột, $K$ là số bước tối đa con ếch có thể nhảy). Theo quy tắc cộng Big-O thì lấy theo thành phần lớn nhất, nên tổng quát là $O(N \cdot K)$.

Không gian$O(N)$

Thời gian$O(N \cdot K)$

Trường hợp xấu nhất mọi dữ liệu đều chạm ngưỡng tối đa: $N = 10^5$, $K = 100$ thì số lần lặp là $10^5 + 10^7 = 10{,}100{,}000$ (10 triệu 100 ngàn). Với giới hạn 2 giây thì số lần lặp được phép khoảng $10^8$ (100 triệu), cao lắm là $2 \cdot 10^8$, nên cách này ít hơn cả 10 đến 20 lần, chắc chắn không sợ TLE. Thậm chí nếu đề chỉ cho 1 giây (ngưỡng khoảng $(3 \text{ đến } 5) \cdot 10^7$, cao lắm $10^8$) thì cách làm này vẫn ít hơn ngưỡng từ 3 đến 10 lần.

Bạn nào code Python để ý

10 triệu phép tính là "nhẹ nhàng" với C++ (mình đo khoảng 0.2 giây), nhưng với Python thì khác: bản Python ở trên mình đo với $N = 10^5$, $K = 100$ mất khoảng 18 giây – sẽ TLE ở các test lớn. Viết gọn vòng trong bằng min([...]) trên list comprehension thì cũng chỉ còn khoảng 9 giây. Bài này các bạn nên nộp C++ nha (hoặc chọn PyPy nếu hệ thống chấm có hỗ trợ).

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output của 4 sample, và đã được so với code vét cạn (thử mọi tập hòn đá dừng chân hợp lệ) trên 400 bộ test ngẫu nhiên nhỏ ($2 \le N \le 12$, $K$ từ $1$ đến $100$) – khớp hết. Với $N = 10^5$, $K = 100$: cách 2 bản C++ chạy khoảng 0.2 giây, bản Python khoảng 18 giây; cách 1 (đệ quy) bản C++ với $N = 30$, $K = 3$ đã mất khoảng 0.8 giây, với $N = 40$, $K = 40$ chạy quá 10 giây chưa xong.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇