Hay un árbol con N Nodes y el Node 1 es el Node raíz. Cada nudo del árbol puede contener frutos o no.
Inicialmente, estás en el Node raíz y comienzas a trepar al árbol.
Puede saltar de un Node a cualquier Node en el mismo nivel (es decir, la altura de los Nodes desde la raíz es la misma).
Durante la escalada desde el Node raíz, solo puede realizar saltos K máximos. (K < 20)
Ahora tienes que trepar al árbol (desde el Node raíz-> cualquier Node de hoja) de tal manera que puedas recolectar el máximo número de frutas.
Ejemplo :
Input Tree : Number of Nodes N = 12 Number of jumps allowed : 2 Edges: 1 2 1 3 2 4 2 5 5 9 9 10 9 11 11 12 3 7 7 6 7 8 no of node having fruit(nf) : 8 Nodes Containing Fruits(lvn) : 2 4 5 7 8 9 11 12 Output: 7
Árbol para el caso de prueba anterior:
Explicación:
Enfoque: La idea es usar DFS para crear una lista de adyacencia de altura de los Nodes y almacenar los padres. Luego use otro dfs para calcular el número máximo de Nodes especiales que se pueden alcanzar usando el siguiente estado de dp:
dp[current_node][j] = max( max{ dp[child_i][j], for all children of current_node }, max{ dp[node_at_same_height_i][j - 1], for all nodes at same height as current_node} )
Por lo tanto, dp[Root_Node][Total_no_of_Jumps] da la respuesta al problema.
A continuación se muestra la implementación del enfoque anterior:
// Program to demonstrate tree traversal with // ability to jump between nodes of same height #include <bits/stdc++.h> using namespace std; #define N 1000 vector<int> H[N]; // Arrays declaration int Fruit[N]; int Parent[N]; int dp[N][20]; // Function for DFS void dfs1(vector<int> tree[], int s, int p, int h) { Parent[s] = p; int i; H[h].push_back(s); for (i = 0; i < tree[s].size(); i++) { int v = tree[s][i]; if (v != p) dfs1(tree, v, s, h + 1); } } // Function for DFS int dfs2(vector<int> tree[], int s, int p, int h, int j) { int i; int ans = 0; if (dp[s][j] != -1) return dp[s][j]; // jump if (j > 0) { for (i = 0; i < H[h].size(); i++) { int v = H[h][i]; if (v != s) ans = max(ans, dfs2(tree, v, Parent[v], h, j - 1)); } } // climb for (i = 0; i < tree[s].size(); i++) { int v = tree[s][i]; if (v != p) ans = max(ans, dfs2(tree, v, s, h + 1, j)); } if (Fruit[s] == 1) ans++; dp[s][j] = ans; return ans; } // Function to calculate and // return maximum number of fruits int maxFruit(vector<int> tree[], int NodesWithFruits[], int n, int m, int k) { // reseting dp table and Fruit array for (int i = 0; i < N; i++) { for (int j = 0; j < 20; j++) dp[i][j] = -1; Fruit[i] = 0; } // This array is used to mark // which nodes contain Fruits for (int i = 0; i < m; i++) Fruit[NodesWithFruits[i]] = 1; dfs1(tree, 1, 0, 0); int ans = dfs2(tree, 1, 0, 0, k); return ans; } // Function to add Edge void addEdge(vector<int> tree[], int u, int v) { tree[u].push_back(v); tree[v].push_back(u); } // Driver Code int main() { int n = 12; // Number of nodes int k = 2; // Number of allowed jumps vector<int> tree[N]; // Edges addEdge(tree, 1, 2); addEdge(tree, 1, 3); addEdge(tree, 2, 4); addEdge(tree, 2, 5); addEdge(tree, 5, 9); addEdge(tree, 9, 10); addEdge(tree, 9, 11); addEdge(tree, 11, 12); addEdge(tree, 3, 7); addEdge(tree, 7, 6); addEdge(tree, 7, 8); int NodesWithFruits[] = { 2, 4, 5, 7, 8, 9, 11, 12 }; // Number of nodes with fruits int m = sizeof(NodesWithFruits) / sizeof(NodesWithFruits[0]); int ans = maxFruit(tree, NodesWithFruits, n, m, k); cout << ans << endl; return 0; }
7
Complejidad de tiempo: O(n*n*k) (peor caso, por ejemplo: árbol de 2 niveles con la raíz que tiene n-1 Nodes secundarios)
Publicación traducida automáticamente
Artículo escrito por narutouzumaki696 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA