考えたこと
愚直に求めようとすると,それぞれの町で2通りあるので計算量が以上になって間に合わなさそうなので,DPを使って解く.
普通にDPするだけ
町の数日程のDPテーブルを作る
n, m = map(int, input().split()) d = [int(input()) for _ in range(n)] c = [int(input()) for _ in range(m)] dp = [[float('inf')] * (n+1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = 0 for i in range(1, m+1): for j in range(1, n + 1): dp[i][j] = min(dp[i][j], dp[i-1][j], dp[i-1][j-1] + d[j - 1] * c[i - 1]) print(dp[-1][-1])