Con Ếch 2 (FROG2)
Có tảng đá, được đánh số . Với mỗi (), tảng đá có chiều cao là . Một con ếch ban đầu ở tảng đá . Nó sẽ lặp lại hành động sau một số lần để đến được tảng đá : Nếu con ếch hiện đang ở trên đá , nó có thể nhảy đến bất kỳ tảng đá nào trong các đá . Chi phí phát sinh khi nhảy từ đá sang đá là .
Yêu cầu: Tìm tổng chi phí tối thiểu có thể để đến được tảng đá .
Dữ liệu:
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên .
Kết quả: In ra chi phí tối thiểu.
Ví dụ:
Dữ liệu:
5 3
10 30 40 50 20
Kết quả:
30
Giải thích: Một đường đi tối ưu là .
- Chi phí từ là .
- Chi phí từ là . Tổng chi phí là .
Giới hạn:
Yêu cầu: Code sau chưa đúng, hãy chỉ ra lỗi sai và tạo ra một testcase mà code này cho kết quả sai.
Testcase gồm 2 file:
FROG2.INP: là dữ liệu vào.
FROG2.OUT là kết quả đúng.
Code C++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
// Khai báo hằng số vô cùng để tìm min
const int INF = 1e8; // 100,000,000
int main() {
// Tối ưu tốc độ nhập xuất
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
if (!(cin >> N >> K)) return 0;
vector<int> h(N + 1);
for (int i = 1; i <= N; ++i) {
cin >> h[i];
}
// Mảng quy hoạch động, khởi tạo giá trị vô cùng
vector<int> dp(N + 1, INF);
// Chi phí tại điểm xuất phát là 0
dp[1] = 0;
for (int i = 2; i <= N; ++i) {
// Thử nhảy từ các tảng đá trước đó (tối đa K bước)
for (int j = 1; j <= K; ++j) {
if (i - j >= 1) {
int cost = dp[i - j] + abs(h[i] - h[i - j]);
if (cost < dp[i]) {
dp[i] = cost;
}
}
}
}
cout << dp[N] << endl;
return 0;
}