This article solves the problem of spiral books. The language is python. I also wrote a bite memo, so please refer to it.
chapter2
Maximum Profit
n = int(input())
price = []
for k in range(n):
price.append(int(input()))
min_price = 1000000001
max_pro = -200000
for i in range(n):
max_pro = max(max_pro, price[i]-min_price)
min_price = min(price[i], min_price)
print(max_pro)
11.4 Chain matrix product
First, it is difficult to formulate a recurrence formula. Furthermore, it is difficult to think about the order of calculation. The order of calculation is [here](https://aotamasaki.hatenablog.com/entry/2019/11/03/%E8%9E%BA%E6%97%8B%E6%9C%AC%E3%82 % 92 Python% E3% 81% A7% E8% A7% A3% E3% 81% 8F_Part2 # P257-ALDS1_10_B-Matrix-Chain-Multiplication).
n = int(input())
p = []
for t in range(n):
a, b = map(int, input().split())
if t == 0:
p.append(a)
p.append(b)
'''
dp[i][j]Is Mi~Minimum number of multiplications to calculate Mj
'''
dp = [[float('inf')] * (n+1) for j in range(n+1)]
for k in range(n+1):
dp[k][k] = 0
dp[0][k] = 0
dp[k][0] = 0
#l is the distance from the diagonal component
for l in range(1,n+1):
for i in range(0,n-l+1):
j = i + l
for k in range(0,j-i):
dp[i][j] = min(dp[i][j], dp[i][i+k] + dp[i+k+1][j] + p[i-1] * p[j] * p[i+k])
print(dp[1][n])
'''
input
6
30 35
35 15
15 5
5 10
10 20
20 25
output
15125
'''
Recommended Posts