[Python] DFS AGC044A

AGC044A Minimum cost search problem

Repeat the same operation ⇒Recursion

The content is quoted below, with sufficient explanation. This post is a private note. Try to solve the A problem "Pay to Win" of AGC044 with Python

Sample code


T = int(input())
 
for t in range(T):
    N, A, B, C, D = map(int, input().split())
    memo = {}
 
    def dist(n):
        if n == 0:
            return 0
        if n == 1:
            return D
        if n in memo:
            return memo[n]
        
        ret = min(
            D * n,
            D * abs(n - n//5*5) + C + dist(n//5),
            D * abs(n - (n+4)//5*5) + C + dist((n+4)//5),
            D * abs(n - n//3*3) + B + dist(n//3),
            D * abs(n - (n+2)//3*3) + B + dist((n+2)//3),
            D * abs(n - n//2*2) + A + dist(n//2),
            D * abs(n - (n+1)//2*2) + A + dist((n+1)//2)
        )
 
        memo[n] = ret
        return ret

    print(dist(N))

Recommended Posts

[Python] DFS AGC044A
Python
[Python] DFS (Depth-first Search) ATC001A
[Python] DFS (Depth-first Search) ABC157D
kafka python
Python Summary
Built-in python
Python comprehension
Python technique
Studying python
Python 2.7 Countdown
Python FlowFishMaster
Python service
python tips
python function ①
Python basics
Python memo
ufo-> python (3)
Python comprehension
install python
Python basics ④
Python Memorandum 2
python memo
Python Jinja2
Python increment
atCoder 173 Python
[Python] function
Python installation
python tips
Installing Python 3.4.3.
Python memo
Python iterative
Python algorithm
Python2 + word2vec
[Python] Variables
Python functions
Python sys.intern ()
Python tutorial
Python decimals
Python summary
[Python] Sort
Python basics ③
python log
[Scraping] Python scraping
Python update (2.6-> 2.7)
python memo
Python memorandum
Python # sort
ufo-> python
Python nslookup
python learning
Hannari Python 2020
[Rpmbuild] Python 3.7.3.
Prorate Python (1)
python memorandum
Download python
python memorandum
Python memo
started python
python quiz
Python encoding