Ant book in python: page 49 Fence Repair


# 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) and argmin (1) were good.

It may be better to write articles for each chapter instead of each question.

The point is ・ No matter how you cut, the final number of cuts does not change. ・ Each cut divides the board into independent blocks ・ Cost is proportional to the depth at which the board is cut out in each block.

Therefore, in the case of L = {a, b, c} (a <= b <= c), it is best to cut out c alone, and the cost is (a + b + c) + (a + b).

If the number of elements of L is odd, the deepest part of the tree will look like this, so you can pair a and b.

When the number of elements of L is even When L = {a, b, c, d} (a <= b <= c <= d), when comparing the cost of cutting out two parts-> two parts and d

2(a + b + c + d )
When (a + b + c + d) + (a + b + c) + (a + b) = 3(a+b) + 2c + d

It cannot be said unconditionally which is correct (depending on the values of a, b, and d).

However, in either case, a and b are the final pair at the lowest cost.

If a and b are paired (ab), Since it becomes a board of L = {ab, c, d}, it can be reduced to an odd number, and the next combination is L = {abc, d}.

Even if L = {a, b, c, d, e} is considered when the number of elements is 5, a and b are always paired at the minimum cost, so it can be finally dropped when it is 3.

So, if you make a pair of the smallest two, it's ok.

Recommended Posts

Ant book in python: page 49 Fence Repair
Ant book in python: page 42 coin problem
Ant book in python: page 43 Interval scheduling
Ant book in python: page 47 Saruman's Army (POJ 3069)
Ant book in python: Sec. 2-5 Graph
Ant book in python: page 45 Dictionary order minimum problem (POJ3617)
Ant book in python: Priority queue self-implementation
Ant book in python: Sec.2-5 Dijkstra's algorithm
Ant book in python: Sec. 2-5 Graph (preparation)
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
I couldn't understand Fence Repair of the ant book easily, so I will follow it in detail.
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Page cache in Python + Flask with Flask-Caching
Ant book with python (chapter3 intermediate edition ~)
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Unittest in python
Epoch in Python
Discord in Python
Sudoku in Python
DCI in Python
quicksort in python
nCr in python
Plink in Python
Constant in python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
Create a new page in confluence with Python
N-gram in python
LINE-Bot [0] in Python
Disassemble in Python
Reflection in Python
Use a custom error page in python / tornado
Constant in python
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Python reference page
Quad-tree in Python
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
Solve "AtCoder version! Ant book (beginner)" with Python!
LiNGAM in Python
Flatten in python
flatten in python
Make each PowerPoint page an image file in Python
How to add page numbers to PDF files (in Python)
Implemented the algorithm of "Algorithm Picture Book" in Python3 (Heapsort)
Sorted list in Python