Leśne zwierzęta – omówienie zadania

Leśne zwierzęta – omówienie zadania

Szczegółowe omówienie zadania Leśne zwierzęta:

Link do powyższego omówienia zadania Leśne zwierzęta:
https://youtu.be/pSJD2xzdLZ0?t=1500

Link do treści zadania Leśne zwierzęta oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/lz/site


Powyższe rozwiązanie zadania Leśne zwierzęta wykorzystuje 2 techniki:
* Programowanie dynamiczne
* Na później


Zadanie pochodzi z finału XII Młodzieżowej Olimpiady Informatycznej:
https://szkopul.edu.pl/task_archive/oig/

Zadanie Omawia Tomek Kwiatkowski – finalista Olimpiady Informatycznej:
https://youtu.be/2ZL03PfmQiI?t=2175


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


Kod C++ programu Leśne zwierzęta, który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 1000*1000 + 7;

ll suma[MAXN];
ll pocz[MAXN];
ll dp[MAXN];

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

	int liczbaDzialek, liczbaZwierzat, cenaDzialki;
	cin >> liczbaDzialek >> liczbaZwierzat >> cenaDzialki;

	for (int i = 1; i <= liczbaZwierzat; i++) {
		int a, b, k;
		cin >> a >> b >> k;

		pocz[a] += k;
		suma[a] += k;
		suma[b + 1] -= k;
	}

	for (int i = 1; i <= liczbaDzialek; i++)
		suma[i] += suma[i - 1];

	ll wynik = 0;
	for (int i = 1; i <= liczbaDzialek; i++) {
		dp[i] = max(dp[i - 1] + (ll)cenaDzialki - pocz[i],
					(ll)cenaDzialki - suma[i]);

		wynik = max(wynik, dp[i]);
	}
	cout << wynik << '\n';
	return 0;
}
Kod C++ programu Leśne zwierzęta, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz