Poniżej znajduje się kod C++ realizujący optymalny algorytm zadania Boxes with souvenirs omówiony w powyższym filmie.
Gotowy plik *.cpp z optymalnym algorytmem zadania Boxes with souvenirs możesz również pobrać kilkając w ten link:
Plik C/C++ realizujący optymalny algorytm
#include
using namespace std;
typedef long long ll;
const int N=1e7+10;
const ll I=1000LL*1000LL*1000LL*1000LL*1000LL*1000LL;
int Wczytaj[N];
ll DPL[N];
ll DPP[N];
void WczytajDane(int &n, int &k, int &l){
cin>>n>>k>>l;
for(int i=1; i<=n; i++) cin>>Wczytaj[i];
}
void LiczDPL(int n, int k){
for(int i=1; i<=n; i++){
if(i<=k){
DPL[i]=(ll)Wczytaj[i]*2LL;
continue;
}
DPL[i]=(ll)Wczytaj[i]*2LL+DPL[i-k];
}
}
void LiczDPP(int n, int k, int l){
for(int i=n; i>=1; i--){
if( n-i+1 <= k){
DPP[i]=(ll)( l-Wczytaj[i] )*2LL;
continue;
}
DPP[i]=(ll)( l-Wczytaj[i] )*2LL+DPP[i+k];
}
}
ll LiczWynik(int n, int k, int l){
ll wynik=I;
if(k>=n) wynik=min(wynik, (ll)l);
for(int i=1; i+k-1<=n; i++) wynik=min(wynik, DPL[i-1]+DPP[i+k]+(ll)l);
for(int i=1; i<=n+1; i++) wynik=min(wynik, DPL[i-1]+DPP[i]);
return wynik;
}
int main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, k, l;
WczytajDane(n, k, l);
LiczDPL(n,k);
LiczDPP(n,k,l);
cout<
Koło informatyczne Staszica
Film powstał w ramach otwartego koła informatycznego w XIV Liceum Ogólnokształcącym im Stanisława Staszica w Warszawie.
Zadanie omawia Jędrzej Olkowski, laureat Olimpiady Informatycznej Licealistów, laureat Międzynarodowej Bałtyckiej Olimpiady Informatycznej, uczestnik koła.
