ABC251E - Tahakashi and Animals

解法1

考え方（貰うDP）

「dp[i] = $i$までの全てに餌をあげる方法を決めたときの最小の合計コスト」とすると，「$i$と$i + 1$に餌をあげる場合」と「$i + 1$と$i + 2$に餌をあげる場合」の小さい方がdp[i + 1]なので

\begin{aligned}
& \mathrm{dp}[i + 1] \\
&= \min(\mathrm{dp}[i - 1] + A[i], \mathrm{dp}[i] + A[i + 1])
\end{aligned}

となる．ここで，$\mathrm{dp}[i] + A[i] (\geq \mathrm{dp}[i - 1] + A[i])$は無駄なので省いている．

初期化の仕方（dp[0]の決め方）として，「$0$と$1$に餌をあげる場合」と「$N - 1$と$0$に餌をあげる場合」の2通りがあるので，両方試して小さい方を出力する．

回答例（貰うDP）

N = int(input())
A = list(map(int, input().split()))

dp = [1 << 60] * N
dp[0] = dp[1] = A[0]
for i in range(1, N - 1):
    dp[i + 1] = min(dp[i - 1] + A[i], dp[i] + A[i + 1])

ans = dp[N - 1]

dp = [1 << 60] * N
dp[N - 1] = dp[0] = A[N - 1]
for i in range(N - 2):
    dp[i + 1] = min(dp[i - 1] + A[i], dp[i] + A[i + 1])

ans = min(ans, dp[N - 2])
print(ans)

【参考】Submission #31666881 - Panasonic Programming Contest 2022(AtCoder Beginner Contest 251)

考え方（配るDP）

遷移を

\begin{aligned}
& \mathrm{dp}[i + 1] = \min(\mathrm{dp}[i + 1], \mathrm{dp}[i] + A[i + 1]) \\
& \mathrm{dp}[i + 2] = \min(\mathrm{dp}[i + 2], \mathrm{dp}[i] + A[i + 1]) \\
\end{aligned}

とすればよい．

回答例（配るDP）

ループ範囲に注意．

N = int(input())
A = list(map(int, input().split()))

dp = [1 << 60] * N
dp[0] = dp[1] = A[0]
for i in range(N - 1):
    dp[i + 1] = min(dp[i + 1], dp[i] + A[i + 1])
    if i + 2 > N - 1:continue
    dp[i + 2] = min(dp[i + 2], dp[i] + A[i + 1])

ans = dp[N - 1]

dp = [1 << 60] * N
dp[N - 1] = dp[0] = A[N - 1]
for i in range(N - 2):
    dp[i + 1] = min(dp[i + 1], dp[i] + A[i + 1])
    if i + 2 > N - 2:continue
    dp[i + 2] = min(dp[i + 2], dp[i] + A[i + 1])

ans = min(ans, dp[N - 2])
print(ans)

解法2

考え方（貰うDP）

「dp[i][j] = $A[i]$まで決めたときに$A[i]$を選んでいるならj = True選んでいないならj = Falseとする．

遷移は

\begin{aligned}
& \mathrm{dp}[i + 1][\mathrm{False}]
= \mathrm{dp}[i][\mathrm{True}] \\
& \mathrm{dp}[i + 1][\mathrm{True}] \\
& = \min(\mathrm{dp}[i][\mathrm{False}] + A[i + 1], \mathrm{dp}[i][\mathrm{True}] + A[i + 1])
\end{aligned}

回答例（貰うDP）

N = int(input())
A = list(map(int, input().split()))

dp = [[1 << 60] * 2 for _ in range(N)]
dp[0][1] = A[0]
for i in range(N - 1):
    dp[i + 1][0] = dp[i][1]
    dp[i + 1][1] = min(dp[i][0] + A[i + 1], dp[i][1] + A[i + 1])

ans = min(dp[N - 1])

dp = [[1 << 60] * 2 for _ in range(N)]
dp[0][0] = 0
for i in range(N - 1):
    dp[i + 1][0] = dp[i][1]
    dp[i + 1][1] = min(dp[i][0] + A[i + 1], dp[i][1] + A[i + 1])

ans = min(ans, dp[N - 1][1])

print(ans)

N = int(input())
A = list(map(int, input().split()))

dp = [[1 << 60] * 2 for _ in range(N)]
dp[0][1] = A[0]
for i in range(N - 1):
    dp[i + 1][0] = dp[i][1]
    dp[i + 1][1] = min(dp[i][0] + A[i + 1], dp[i][1] + A[i + 1])

ans = min(dp[N - 1])

dp = [[1 << 60] * 2 for _ in range(N)]
dp[N - 1][1] = A[N - 1]
dp[0][0] = A[N - 1]
dp[0][1] = A[N - 1] + A[0]
for i in range(N - 2):
    dp[i + 1][0] = dp[i][1]
    dp[i + 1][1] = min(dp[i][0] + A[i + 1], dp[i][1] + A[i + 1])

ans = min(ans, min(dp[N - 2]))

print(ans)