Giełda – Omówienie zadania – Programowanie Dynamiczne

Szczegółowe omówienie zadania Giełda:

Link do powyższego omówienia zadania Giełda: https://youtu.be/H0SxPD5xYvI?t=1197
Omówienie kodu zadania Giełda: https://youtu.be/TSj1TsKUSR8?t=4508
Złożoność rozwiązania: https://youtu.be/TSj1TsKUSR8?t=4453
Link do treści zadania Giełda i możliwości umieszczania rozwiązań: https://szkopul.edu.pl/problemset/problem/H5QP-C9e69Klb8r65qXbJXN7/site/


Zadanie Giełda pokazuje programowanie dynamiczne: https://youtu.be/H0SxPD5xYvI?t=955
Wyjaśnienie programowania dynamicznego w quizie: https://youtu.be/TSj1TsKUSR8?t=331
Kluczowa obserwacja w zadaniu Giełda: https://youtu.be/TSj1TsKUSR8?t=2220
Przyspieszenie algorytmu: https://youtu.be/TSj1TsKUSR8?t=3102
Na czym polega programowanie dynamiczne na przykładzie zadania Giełda?
https://youtu.be/H0SxPD5xYvI?t=3128
Czym różni się programowanie dynamiczne od algorytmów zachłannych: https://youtu.be/TSj1TsKUSR8?t=5144


Zadanie z konkurs Mistrz Programowania: https://youtu.be/DI0lRjXoCGc?t=16
Wszystkie zadania z konkursu: https://oki.org.pl/mistrz-programowania-2022/


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 "Giełda", który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 1e6 + 7;

long long dp[MAXN];
int wartosc[MAXN];

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

	int n, oplata;
	cin >> n >> oplata;
	for (int i = 1; i <= n; ++i)
		cin >> wartosc[i];

	dp[0] = 0;
	long long maxx = -1e9;
	for (int i = 1; i <= n; ++i) {
		dp[i] = max(dp[i - 1], wartosc[i] - oplata + maxx);
		maxx = max(maxx, dp[i - 1] - wartosc[i]);
	}
	cout << dp[n] << '\n';
	return 0;
}
Kod C++ programu "Giełda", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu Giełda, który otrzymuje 100%:

def solve():
	n, oplata = map(int, input().split())
	wartosc = list(map(int, input().split()))

	dp = [0] * (n + 1)

	maxx = -1e9
	for i in range(1, n + 1):
		dp[i] = max(dp[i - 1], wartosc[i - 1] - oplata + maxx)
		maxx = max(maxx, dp[i - 1] - wartosc[i - 1])
	print(dp[n])

solve()

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz