Module: Dynamische Programmierung in Graphen


Problem

1 /7


Theory Click to read/hide

In der Dynamik der Unterstützung verarbeiten wir die Tops auf "normale Weise in die Tiefe". Indem wir den Baum in die Tiefen umkreisen, unterstreichen wir die Bedeutung der Dynamik, indem wir die Werte der Unterstützung der Kinder verwenden, die wir bereits im Bypass gezählt haben.

Zum Beispiel werden wir folgendes entscheiden: Dana binäre Baum (mit maximal zwei Kindern an jeder Spitze) mit einem Gewicht (möglicherweise negativ). Wir nennen die Gewichte der Gipfel auf dieser Straße. Das maximale Gewicht des einfachen Pfades in diesem Baum muss gefunden werden.

Zuerst legen wir einen Baum hinter eine Spitze (z.B. oben mit Nummer 1).
Wir werden zwei Arten von Möglichkeiten betrachten:
(1) Vertikale Wege - eines der Enden ist die Vorderkante des zweiten Endes.
(2) Horizontale Wege - keines der Enden der Reise ist ein Vorfahren der zweiten.
Jeder Pfad in einem Baum ist einer dieser Arten.

Jeder horizontale Pfad hat einen höheren Punkt, der am wenigsten verbreitete Ahnen der beiden Enden der Reise. Für die vertikale Fahrt ist der höchste Punkt einfach der Endkrieg.
Um alle möglichen Wege zu betrachten, werden wir die höchsten Punkte des Weges überqueren. Sagen wir, wir haben ein paar Tops. Wenn dies der höchste Punkt eines vertikalen Pfades ist, ist das zweite Ende die Spitze, die irgendwo im Hintergrund einer aufgenommenen Spitze liegt. Wenn dies der höchste Punkt der horizontalen Strecke ist, liegt das erste Ende der Straße in der Unterstützung des linken Kindes, und das andere Ende liegt in der Unterstützung des rechten Kindes (und sonst ist der Gipfel von v nicht wirklich der höchste Punkt). Wir werden es benutzen, um die besten Wege herauszufinden.

Dynamische Programmierung: dp[v] - maximales Gewicht vertikal die Reise mit dem höchsten Punkt in der Spitze von v.
Berechnung dp[v] - Es gibt drei Möglichkeiten, einen optimalen vertikalen Weg mit einem oberen Punkt v zu bauen:
(1) Eine Straße, die nur aus der oberen v besteht. Dann ist das Gewicht nur die Spitze des v. Dies kann als Primärwert der Dynamik verwendet werden.
(2) Nehmen Sie den optimalen vertikalen Weg mit dem höchsten Punkt im linken Kind und erweitern Sie ihn nach oben. Der Wert dieser Route ist dp[left] + w(v).
(3) Nehmen Sie den optimalen vertikalen Weg mit dem höchsten Punkt im rechten Kind und erweitern Sie ihn nach oben. Der Wert dieser Route ist dp[right] + w(v).

Wenn wir das maximale dp[v] nehmen, werden wir das maximale Gewicht der vertikalen Pfade kennen.
Wir müssen die horizontalen Pfade berücksichtigen. Sie können auch von dp betrachtet werden. Durch die Festlegung der Oberseite v als der höchste Punkt der horizontalen Pfade sollte die dp[link] + w(v) + dp[right] einfach als zwei vertikale Pfade von verschiedenen Stützen an der Spitze verbunden werden. Angesichts dieser Werte können wir das maximale Gewicht unter allen Strecken bestimmen.

Es ist alles möglich, dies durch den Umfang des Baumes in die Tiefe zu lösen. Details in Code:

/ Stauraum aus Holz
TreeNode {
int val;
TreeNode* links;
TreeNode* rechts;
TreeNode() : val(0), links(nullptr), rechts(nullptr) {}
TreeNode(int x) : val(x), links(nullptr), rechts(nullptr) {}
TreeNode(int x, TreeNode* links, TreeNode* rechts) : val(x), links(links), rechts(rechts) {}
?

/ globale Antwort - Wert des Maximums
int res;

/ / dp[v] = maximaler Abstandswert
/ mit einem höheren Top v und einem unteren irgendwo in der Spitze von v

/ anstatt dp zu halten
// Lassen Sie uns es einfach als Wert des Vortrags zurückgeben (in die Tiefe)
int calc(TreeNode* v)

/ vert ist der vertikale Weg von oben v, in der Tat der Wert dp[v]
/ Primärwert - Wert in Top v, d.h. nur von oben v
int vert = v-stateval;

/ hor ist ein horizontaler Pfad, mit einem Spitzenpunkt (lca)
/ Initiierter Wert in Top v
int hor = v-stateval;

/ Wenn das linke Kind existiert
wenn (v-nationalleft!= nullptr) {~}
int d = calc(v-nationalleft); // berechnet den dynamischen Wert des linken Kindes
vert = max(vert, d + v-stateval); // Aktualisieren Sie den vertikalen Pfad als Fortsetzung des Pfades des linken Kindes
hor += d; // den linken Zweig der horizontalen Route hinzufügen
♪

/ wenn das richtige Kind existiert
wenn (v-nationalright!= nullptr) {
int d = calc(v-priright); // gezählt die Dynamik des linken Kindes
vert = max(vert, d + v-nationalval); // Aktualisieren Sie den vertikalen Pfad als Fortsetzung des Pfades des rechten Kindes
Hor += d; // Den rechten Zweig der horizontalen Route hinzufügen
♪

/ Erneuern Sie die globale Reaktion durch den vertikalen Weg mit dem höchsten Punkt v
res = max(res, vert);

/ Erneuern Sie die globale Reaktion durch den horizontalen Pfad mit dem höchsten Punkt (lca) in v
res = max(res, hor);

/ Rücksetzen der Peakdynamik v
Rückkehr vert;
♪

int maxPathSum (TreeNode* Wurzel) {
// Initialer Maximalwert gleich Null - leere Straße ohne Spitze
res = 0;

// Beginnen Sie tief
calc(root)

// jetzt relevant
zurück;
♪

Problem

Mirko wurde CEO eines großen Unternehmens. Das Unternehmen beschäftigt N Personen, die 1 bis N sind, mit Mirko selbst mit der Nummer 1. Alle Arbeiter außer Mirko haben einen Vorgesetzten. Der Chief kann mehrere Untergebene haben, aber nicht mehr als eine seiner Vorgesetzten.

Wenn Mirko einen Auftrag von Investoren erhält, übergibt er ihn an seine Unterordnung mit der niedrigsten Zahl. Die Unterordnung überträgt sie auch an seine Unterordnung mit der kleinsten Zahl, und so weiter, bis die Aufgabe an einen unglücklichen Mitarbeiter übertragen wird, ohne Untergebene, die sie ausführen müssen.
Dieser Arbeiter bekommt 1 Münze, sein Chef bekommt zwei Münzen, der Chef bekommt drei Münzen und so weiter. Wer auch immer der Job tat, erkennt, wie unfair dieses kapitalistische System ist und kündigt.

Mirko bekommt Aufträge, bis nur ein Mitglied im Unternehmen ist, Mirko selbst. Dann führt er diese Mission durch, bekommt 1 Münze und verlässt das Unternehmen.

Er fragte sich, wie viele Münzen jeder Ex-Staff erhalten hatte. Hilf ihm dabei.

Eingabe:
Die erste Zeile enthält eine natürliche Zahl von N (1 ≤ N ≤ 2105.() - Anzahl der Beschäftigten. Die nächste Zeile enthält N-1 Zahlen a2, a3...an (1 ≤ a)I i), aI - Stabschef.

Ausgangsdaten:
Holen Sie N Meißel aus, die i-Nummer sollte bedeuten, wie viele Münzen die i.

Beispiele:
EingangsdatenAusgangsdaten
3
1		Artikel 1
5.
1 2 4		Artikel 1

Beschreibung:

Das zweite Beispiel wird beschrieben.

Mirko gibt den ersten Auftrag an den Arbeiter 2, der ihn an den Arbeiter 3 übergibt, der den Auftrag erfüllt. So erhält der Arbeiter 3 eine Münze, der Mitarbeiter 2 ist zwei Münzen, und der Mitarbeiter 1, Mirko selbst, ist drei Münzen. Danach wird der Arbeiter 3 entlassen.
Mirko gibt einen zweiten Auftrag an den Arbeiter 2, der ihn dem Arbeiter 4 übergibt, der sofort den Auftrag an den Arbeiter 5 überträgt, der den Auftrag erfüllt. Danach erhält ein Arbeiter 5 eine Münze, ein Angestellter 4 zwei Münzen, ein Angestellter 2 drei Münzen, und Mirko erhält vier Münzen. Mitarbeiter 5 wird gefeuert.
Nach der dritten Zuordnung erhält der Arbeiter 4 eine Münze, der Arbeiter 2 erhält zwei Münzen, und Mirko erhält drei Münzen, wonach der Arbeiter 4 entlassen wird.
Nach dem vierten Auftrag erhält der Arbeiter 2 eine Münze und Mirko erhält zwei Münzen, und der zweite Mitarbeiter wird entlassen.
Schließlich wird die fünfte Mission von Mirko selbst durchgeführt, eine Münze dafür erhalten, und der Prozess wird beendet.

Insgesamt erhielt Mirko 13 Münzen, ein Angestellter 2 - 8 Münzen, ein Angestellter 4 - 3 Münzen und Mitarbeiter 3 und 5 eine Münze.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!