Koraliki – omówienie zadania

Koraliki – omówienie zadania

Szczegółowe omówienie zadania Koraliki:

Link do powyższego omówienia zadania Koraliki
https://youtu.be/d5-CJYYwLuk?t=6427

Link do treści zadania Koraliki:
https://szkopul.edu.pl/problemset/problem/kor/site


Zadanie Koraliki pięknie pokazuje zasadę programowania dynamicznego:
https://youtu.be/NAPLYSpHlNU?t=7197

Dlaczego warto znać programowanie dynamiczne?
https://youtu.be/pSJD2xzdLZ0?t=229


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


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

const int MAX_KORALI = 1e6+7;
int dp[MAX_KORALI];
int korale[MAX_KORALI];
 
int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
 int liczba_koralikow; 
 int i;
 string napis;

 cin >> napis;
 napis = " " + napis;
 liczba_koralikow = napis.size();

 
 for(i = 1; i < liczba_koralikow; i++) {
    if(napis[i] == 'C') 
        korale[i] = 1;
    else
        korale[i] = -1;
 }
 
 for(i = 3; i < liczba_koralikow; i++) {
    //albo bierzemy 3 korale + wynik dla i-3, albo ich nie bierzemy 
    dp[i] = max(korale[i]+korale[i-1]+korale[i-2] + dp[i-3], dp[i-1]);
 }
 cout << dp[liczba_koralikow-1] << "\n";
}
Kod C++ programu Koraliki, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz