DP B
from dynamic programming
DP_B
First, DP to be distributed.
code:python
def solve(N, K, heights):
heights += INF * K
costs = INF * (N + K)
costs0 = 0
for i in range(N - 1):
for k in range(1, K + 1):
costsi + k = min(
costsi + k,
costsi + abs(heightsi + k - heightsi))
return costsN - 1
However, 3TLE.
I removed the function call as follows, but 1 TLE remained
I was thinking of compiling it in Numba.
Submitted by PyPy, 165msec AC
code:python
def solve(N, K, heights):
heights += INF * K
costs = INF * (N + K)
costs0 = 0
for i in range(N - 1):
for k in range(1, K + 1):
newcost = costsi + abs(heightsi + k - heightsi)
if newcost < costsi + k:
costsi + k = newcost
return costsN - 1
Collecting DP 、
1625 ms AC
PyPy 385 ms
code:python
def solve(N, K, heights):
costs = 0 * N
costs0 = 0
for i in range(1, N):
costsi = min(
costsj + abs(heightsi - heightsj)
for j in range(max(i - K, 0), i)
)
8TLE
PyPy 540 ms AC
code:python
def solve(N, K, heights):
costs = None * N
costs0 = 0
def get_cost(i):
if costsi != None:
return costsi
c = min(
get_cost(j) + abs(heightsi - heightsj)
for j in range(max(i - K, 0), i)
)
costsi = c
return c
return get_cost(N - 1)
---
This page is auto-translated from /nishio/DP B. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.