Frog – Omówienie zadania – Programowanie Dynamiczne

Frog – Omówienie zadania – Programowanie Dynamiczne

Szczegółowe omówienie zadania Frog:

Link do powyższego omówienia zadania Frog: https://youtu.be/H0SxPD5xYvI?t=1197
Omówienie kodu zadania Frog: https://youtu.be/H0SxPD5xYvI?t=3775
Złożoność rozwiązania: https://youtu.be/H0SxPD5xYvI?t=3487
Link do treści zadania Frog i możliwości umieszczania rozwiązań: https://atcoder.jp/contests/dp/tasks/dp_a


Zadanie Frog pokazuje programowanie dynamiczne: https://youtu.be/H0SxPD5xYvI?t=955
Na czym polega programowanie dynamiczne na przykładzie zadania Żabka?
https://youtu.be/H0SxPD5xYvI?t=3128
W programowaniu dynamicznym ważny jest strażnik: https://youtu.be/H0SxPD5xYvI?t=3869
Co jest istotne w programowaniu dynamicznym? https://youtu.be/H0SxPD5xYvI?t=4300


Zadanie z platformy AtCoder: https://youtu.be/evtnTwRKtkE?t=5829


Jak się uczyć na podstawie tego zadania? https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz: https://youtu.be/pkLXuuOe_qA?t=3625

Lista zadań z rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Zajęcia: https://oki.org.pl/harmonogram-zajec/
Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109


Kod C++ programu "Frog", który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 1e5 + 7;

int h[MAXN];
int dp[MAXN];
// dp[i] = koszt doskoczenia na kamien i-ty

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> h[i];

	dp[0] = 1e9;
	dp[1] = 0;
	for (int i = 2; i <= n; ++i)
		dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));

	cout << dp[n] << '\n';
	return 0;
}
Kod C++ programu "Frog", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Frog, który otrzymuje 100%:

def solve():
	n, k = map(int, input().split())
	h = [0] + list(map(int, input().split()))

	dp = [1e9] * (n + 1)
	dp[1] = 0
	for i in range(2, n + 1):
		for j in range(1, k + 1):
			if (i < j):
				break
			dp[i] = min(dp[i], dp[i - j] + abs(h[i - j] - h[i]))

	print(dp[n])
solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz