Atcoder Educational DP Contest B - Frog 2
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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~ ~...~ ~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
Output
30
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 5~. Chi phí sẽ là ~|10 - 30| + |30 - 20| = 30~.
Sample 2
Input
3 1
10 20 10
Output
20
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 2 \rightarrow 3~. Chi phí sẽ là ~|10 - 20| + |20 - 10| = 20~.
Sample 3
Input
2 100
10 10
Output
0
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 2~. Chi phí sẽ là ~|10 - 10|= 0~.
Sample 4
Input
10 4
40 10 20 70 80 10 20 70 80 60
Output
40
Giải thích
Một đường đi tối ưu là: ~1 \rightarrow 4 \rightarrow 8 \rightarrow 10~. Chi phí sẽ là ~|40−70|+|70−70|+|70−60|=40~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
include <bits/stdc++.h>
using namespace std;
define ll long long
const int maxn = 1000004; int f[maxn],b[maxn]; int main() { //freopen("DOANXE.INP","r",stdin); //freopen("DOANXE.OUT","w",stdout); iosbase::syncwith_stdio(false); cin.tie(NULL); int n , k; cin >> n >> k; int a[n]; for(int i = 0;i < n;i++){ cin >> a[i]; } f[0] = 0; for(int i = 1;i < n;i++){ f[i] = 1e9; for(int j = i - 1;j >= i - k;j--) { f[i] = min(f[i],f[j] + abs(a[i] - a[j])); } } cout << f[n - 1]; } ủa sao sai v ai chỉ giúp mình với .
Bài toán: Ếch nhảy qua các hòn đá Ý tưởng giải:
code vi du : code
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
cho e xin sol ạ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
ok
sao lại là 1e9 mới ac v mn
dp[i] có thể cộng dồn lên đến gần 1e9 thì để khỏi tạo 1e9 tính dp[i] = min(dp[i], giatri) cho de.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
cho e hỏi tại sao đặt min 1e5 lại sai mà 1e9 lại đúng ạ. Với h[i] <= 1e4 mà.