Domek z kart – Omówienie zadania z finału Olimpiady Informatycznej Gimnazjalistów

Szczegółowe omówienie zadania Domek z Kart:

 

Link do powyższego omówienia zadania Domek z kart:
https://youtu.be/8ChVF4kFsJY?t=827
——-
Link do wszystkich zadań z Olimpiady Informatycznej Juniorów:
https://szkopul.edu.pl/task_archive/oig/
Zadanie Domek z kart pochodzi z II etap Olimpiady Informatycznej Gimnazjalistów (poprzednika OIJ).
Tym niemniej zadanie jest na poziomie I / II etapu Olimpiady Informatycznej Licealistów.
——-

Zadanie Domek z kart realizuje programowanie dynamiczne (dynamik) na drzewie.

Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
——-

#include<bits/stdc++.h>
using namespace std;
constexpr int M=1<<17;
int val[M+7];
int dp[M][21];
void compute(int v, int k, int level){
if(!k) return;
dp[v][1]=val[v];
if(level==1) return;
compute(2*v,k-1,level-1);
compute((2*v)+1,k-1,level-1);
for(int i=2; i<=k; i++){
for(int j=0; j<i; j++) dp[v][i]=max(dp[v][i],dp[2*v][j]+dp[2*v+1][i-j-1]+val[v]);	
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k,a,b,v;
cin>>n>>k;
k/=2;
v=0;
for(int i=0; i<n; i++){
for(int j=0; j<(1<<i); j++){
v++;
cin>>a>>b;
val[v]=a+b;	
}
}
compute(1,k,n);
cout<<dp[1][k];
return 0;
}
Kod C++ programu Domek z kart, który jest omówiony w powyższym filmie i który otrzymuje 100% 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz