# coding: utf-8
import numpy as np
N = raw_input()
L = raw_input()
N, L = map(int, N.split())[0],np.array(map(int, L.split()))
cost = 0
while(1):
argindex = np.argsort(L)
l1 = L[argindex[0]]
l2 = L[argindex[1]]
L = np.delete(L, argindex[0])
L = np.delete(L,argindex[1]-1)
cost += l1 + l2
L = np.append(L, l1 + l2)
if len(L) ==1:
break
print cost
Argmin (0) und Argmin (1) waren gut.
Es kann besser sein, Artikel für jedes Kapitel anstelle jeder Frage zu schreiben.
Der Punkt ist ・ Unabhängig davon, wie Sie schneiden, ändert sich die endgültige Anzahl der Schnitte nicht. ・ Jeder Schnitt teilt die Platte in unabhängige Blöcke ・ Die Kosten sind proportional zur Tiefe, in der das Schneiden der Platte in jedem Block abgeschlossen ist
Daher ist es im Fall von L = {a, b, c} (a <= b <= c) am besten, c allein auszuschneiden, und die Kosten betragen (a + b + c) + (a + b).
Wenn die Anzahl der Elemente von L ungerade ist, sieht der tiefste Teil des Baums so aus, sodass Sie a und b koppeln können.
Wenn die Anzahl der Elemente von L gerade ist Wenn L = {a, b, c, d} (a <= b <= c <= d), wenn Sie die Kosten für das Teilen-> Teilen und Ausschneiden von d vergleichen
2(a + b + c + d )
Wann
(a + b + c + d) + (a + b + c) + (a + b) = 3(a+b) + 2c + d
Es kann nicht unbedingt gesagt werden, was richtig ist (abhängig von den Werten von a, b und d).
In beiden Fällen sind jedoch a und b das letzte Paar zu den niedrigsten Kosten.
Wenn a und b gepaart sind (ab), Da es eine Tafel von L = {ab, c, d} wird, kann es auf eine ungerade Zahl reduziert werden, und die nächste Kombination ist L = {abc, d}
Selbst wenn L = {a, b, c, d, e} berücksichtigt wird, wenn die Anzahl der Elemente 5 beträgt, werden a und b immer zu den minimalen Kosten gepaart, so dass es endgültig gelöscht werden kann, wenn es 3 ist.
Wenn Sie also ein Paar der kleinsten zwei machen, ist das in Ordnung.
Recommended Posts