【yukicoder】No.45 回転寿司

週末yukicoder。

問題

問題はこちら

解法

動的計画法です。
$N$ 個のお寿司が手前に流れてきたときの美味しさの最大を $A _ N$ とします。この時 $A _ 0 = 0$ と定義しておきます。

$N = 1$ の時はお寿司が１つだけなので、そのお寿司を取るしかないので、

$A _ 1 = N$

$N = i \ (2 \leq i \leq N)$ の時について、場合を分けて考えてみます。

$i -1$ 番目のお寿司をとった場合は、 $A _ {i - 1} = (i -2 までの美味しさ) + V _ {i -1}$ となり、お寿司は２連続は取れないので自動的に $A _ i = A _ {i-1}$ の関係になります。

$i -1$ 番目のお寿司をとらなかった場合は、 $A _ {i-1} = A _ {i-2}$ となり、お寿司を３連続取らないと美味しさが損になるのでこの場合は $i$ 番目のお寿司をとった方がいいです。よって $A _ i = A _ {i - 2} + V _ i$ となります。

したがって、 $i$ 番目のお寿司が流れてきたときの美味しさの最大は、

$A _ i = max(A _ {i - 1}, A _ {i - 2} + V _ i)$

となります。

上の考えで $A _ N$ を算出すればOKです。

Python3

コード

N=int(input())
V=list(map(int,input().split()))
if N == 1:
    print(V[0])
else:
    A=[0]*(N+1)
    A[1]=V[0]
    for i in range(2,N+1):
        A[i] = max(A[i-1], A[i-2]+V[i-1])
    print(A[N])