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

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