Problem:


Score : 600 points

Problem Statement

Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:

He never visits a point with coordinate less than 0, or a point with coordinate greater than L.

He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.

He only changes direction at a point with integer coordinate.

Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.

After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:

Put a stone in one of Snuke's ears.

Remove a stone from one of Snuke's ears.

Find the minimum number of operations required when Ringo can freely decide how Snuke walks.

Constraints

1 \leq L \leq 2\times 10^5

0 \leq A_i \leq 10^9(1\leq i\leq L)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

L
A_1
:
A_L

Output

Print the minimum number of operations required when Ringo can freely decide how Snuke walks.

Sample Input 1

4
1
0
2
3

Sample Output 1

1

Assume that Snuke walks as follows:

He starts walking at coordinate 3 and finishes walking at coordinate 4, visiting coordinates 3,4,3,2,3,4 in this order.

Then, Snuke's four ears will contain 0,0,2,3 stones, respectively.
Ringo can satisfy the requirement by putting one stone in the first ear.

Sample Input 2

8
2
0
0
2
1
3
4
1

Sample Output 2

3

Sample Input 3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

Sample Output 3

1



Sample input:
4
1
0
2
3


Sample output:
1

Submission status: Accepted

Solution code:
def main():
    L = int(input())
    A = [int(input()) for _ in range(L)]
    dp = [[0] * 5 for _ in range(L+1)]
    for i in range(L):
        dp[i+1][0] = dp[i][0] + A[i]
        dp[i+1][1] = min(dp[i][:2]) + A[i] % 2 + (2 if A[i] == 0 else 0)
        dp[i+1][2] = min(dp[i][:3]) + (A[i]+1) % 2
        dp[i+1][3] = min(dp[i][:4]) + A[i] % 2 + (2 if A[i] == 0 else 0)
        dp[i+1][4] = min(dp[i][:5]) + A[i]
    print(min(dp[L]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
L = input()
A = [input() for _ in range(L)]

dp = [[float("inf")] * 5 for _ in range(L)]
dp[0][0] = A[0]
dp[0][1] = A[0] % 2 if A[0] > 0 else 2
dp[0][2] = 1 - A[0] % 2
dp[0][3] = A[0] % 2 if A[0] > 0 else 2
dp[0][4] = A[0]

for i in range(L - 1):
    dp[i + 1][0] = dp[i][0] + A[i + 1]
    dp[i + 1][1] = min(dp[i][:2]) + A[i + 1] % 2 if A[i + 1] > 0 else min(dp[i][:2]) + 2
    dp[i + 1][2] = min(dp[i][:3]) + 1 - A[i + 1] % 2
    dp[i + 1][3] = min(dp[i][:4]) + A[i + 1] % 2 if A[i + 1] > 0 else min(dp[i][:4]) + 2
    dp[i + 1][4] = min(dp[i][:5]) + A[i + 1]
print min(dp[-1])

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-11

#DP
L = int(input())
DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    cos = cost(int(input()))
    DP[4] = n[4] + cos[4]
    DP[3] = n[3] + cos[3]
    DP[2] = n[2] + cos[2]
    DP[1] = n[1] + cos[1]
    DP[0] = n[0] + cos[0]

print(min(DP))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-11

#DP

L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

def list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

for i in range(L):
    a = int(input())
    cos = cost(a)
    DP[4] = min(DP[:5]) + cos[4]
    DP[3] = min(DP[:4]) + cos[3]
    DP[2] = min(DP[:3]) + cos[2]
    DP[1] = min(DP[:2]) + cos[1]
    DP[0] = min(DP[:1]) + cos[0]



print(min(DP))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-11

#DP

L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

def list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = int(input())
    cos = cost(a)
    DP = list_add(n, cos)



print(min(DP))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-11

#DP

L = int(input())

DP = [0 for i in range(5)]

def cost(a):
    if a:
        return [a, a%2, (a+1)%2, a%2, a]
    else:
        return [0, 2, 1, 2, 0]

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = int(input())
    cos = cost(a)
    DP[0] = n[0] + cos[0]
    DP[1] = n[1] + cos[1]
    DP[2] = n[2] + cos[2]
    DP[3] = n[3] + cos[3]
    DP[4] = n[4] + cos[4]



print(min(DP))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [0 for i in range(5)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    n = [min(DP[:i+1]) for i in range(5)]
    a = A[i]
    DP[0] = n[0] + cost(0, a)
    DP[1] = n[1] + cost(1, a)
    DP[2] = n[2] + cost(2, a)
    DP[3] = n[3] + cost(3, a)
    DP[4] = n[4] + cost(4, a)



print(min(DP))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    a = A[i]
    DP[i+1][0] = min(DP[i][:1]) + cost(0, a)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, a)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, a)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, a)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, a)



print(min(DP[L]))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, A[i])



print(min(DP[L]))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, i, a):
    if s == 0 or s == 4:
        return a
    elif s == 1 or s == 3:
        if a > 0:
            return a%2
        else:
            return 2
    else:
        return (a+1)%2

for i in range(L):
    DP[i+1][0] = min(DP[i][:1]) + cost(0, i, A[i])
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A[i])
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A[i])
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A[i])
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A[i])



print(min(DP[L]))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[0 for i in range(5)] for j in range(L+1)]

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    DP[i+1][0] = DP[i][0] + cost(0, i, A)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A)



print(min(DP[L]))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[float("inf") for i in range(5)] for j in range(L+1)]
for i in range(5):
    DP[0][i] = 0

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    DP[i+1][0] = DP[i][0] + cost(0, i, A)
    DP[i+1][1] = min(DP[i][:2]) + cost(1, i, A)
    DP[i+1][2] = min(DP[i][:3]) + cost(2, i, A)
    DP[i+1][3] = min(DP[i][:4]) + cost(3, i, A)
    DP[i+1][4] = min(DP[i][:5]) + cost(4, i, A)



print(min(DP[L]))

Submission status: Accepted

Solution code:
import sys
def f(j, a):
    if j == 2:
        return 1 - a%2
    if j % 2:
        return a % 2 if a else 2
    else:
        return a

L = int(input())
A = [0] + [int(sys.stdin.readline()) for _ in [0]*L]
B = [a%2 if a else 2 for a in A]
dp = [[0]*5 for _ in [0]*(L+1)]

for i in range(L):
    for j in range(5):
        dp[i+1][j] = min(dp[i][:j+1]) + f(j, A[i+1])
print(min(dp[-1]))

Submission status: Accepted

Solution code:
import sys


def calc(itr):
    dp = [0]
    turn, no_turn, no_visit = 0, 0, 0
    for a in itr:
        b = a % 2
        new_turn = min(turn, no_visit) + (2 if a == 0 else b)
        new_no_turn = min(turn, no_turn, no_visit) + (b ^ 1)
        new_no_visit = no_visit + a
        dp.append(min(new_turn, new_no_turn, new_no_visit))
        turn, no_turn, no_visit = new_turn, new_no_turn, new_no_visit
    return dp


l = int(input())
aaa = list(map(int, sys.stdin))

dp_f = calc(aaa)
dp_b = calc(reversed(aaa))
dp_b.reverse()

print(min(map(sum, zip(dp_f, dp_b))))

Submission status: Accepted

Solution code:
n=int(input())
zot=lambda x:0 if x==0 else (x+1)%2+1
A=[int(input()) for i in range(n)]
D=[0,0,0,0,0]

for a in A:
  d0 = D[0] + a
  d1 = min(D[:2])+ [2,1,0][zot(a)]
  d2 = min(D[:3])+ [1,0,1][zot(a)]
  d3 = min(D[:4])+ [2,1,0][zot(a)]
  d4 = min(D) + a
  D=[d0,d1,d2,d3,d4]
print(min(D))

Submission status: Accepted

Solution code:
# https://yahoo-procon2019-qual.contest.atcoder.jp/tasks/yahoo_procon2019_qual_d

L = int(input())

A = [int(input()) for _ in range(L)]

INF = int(1e15)
dp = [[INF] * (L + 1) for _ in range(5)]

for i in range(4):
    dp[i][0] = 0

for i in range(L):
    dp[0][i + 1] = dp[0][i] + A[i]  # 全部取り除く
    dp[1][i + 1] = min(dp[j][i] for j in range(2)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[2][i + 1] = min(dp[j][i] for j in range(3)) + (1 if A[i] % 2 == 0 else 0)
    dp[3][i + 1] = min(dp[j][i] for j in range(4)) + (A[i] % 2 if A[i] != 0 else 2)
    dp[4][i + 1] = min(dp[j][i] for j in range(5)) + A[i]  # 全部取り除く


print(min(dp[i][L] for i in range(1, 5)))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for _ in range(L)]
INF = 10**20
DP = [[INF for i in range(5)] for _ in range(L)]
DP[0][0] = A[0]
DP[0][1] = (2 if A[0] == 0 else 1 if A[0] % 2 == 1 else 0)
DP[0][2] = (1 if A[0] % 2 == 0 else 0)
DP[0][3] = (2 if A[0] == 0 else 1 if A[0] % 2 == 1 else 0)
DP[0][4] = A[0]

for i in range(1, L):
    a = A[i]
    DP[i][0] = DP[i-1][0] + a
    DP[i][1] = min(DP[i-1][:2]) + (2 if a == 0 else 1 if a % 2 == 1 else 0)
    DP[i][2] = min(DP[i-1][:3]) + (1 if a % 2 == 0 else 0)
    DP[i][3] = min(DP[i-1][:4]) + (2 if a == 0 else 1 if a % 2 == 1 else 0)
    DP[i][4] = min(DP[i-1]) + a

print(min(DP[L-1]))

Submission status: Accepted

Solution code:
# 参考
# https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4223019

L = int(input())
a_list = [int(input()) for _ in range(L)]

dp = [[0] * 5 for _ in range(L+1)]

for i in range(L):
    a = a_list[i]

    if a > 0:
        even = a % 2
    else:
        even = 2
    odd = (a + 1) % 2

    #0
    dp[i+1][0] = dp[i][0] + a
    #偶数（0であれば0の項目に含まれるはずなので、0より大きい偶数）
    dp[i+1][1] = min(dp[i][:2]) + even
    #奇数（スタートとゴールの間の区間）
    dp[i+1][2] = min(dp[i][:3]) + odd
    #偶数（0であれば0の項目に含まれるはずなので、0より大きい偶数）
    dp[i+1][3] = min(dp[i][:4]) + even
    #0
    dp[i+1][4] = min(dp[i][:5]) + a
print(min(dp[L]))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for _ in range(L)]

dp = [0, 0, 0, 0, 0]
for a in A:
  cost24 = a % 2 if a > 0 else 2
  cost3 = int(a % 2 == 0)
  nextdp = []
  nextdp.append(dp[0] + a)
  nextdp.append(min(dp[:2]) + cost24)
  nextdp.append(min(dp[:3]) + cost3)
  nextdp.append(min(dp[:4]) + cost24)
  nextdp.append(min(dp) + a)
  dp = nextdp

print(min(dp))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for i in range(L)]

INF = float('inf')
dp = [[INF]*5 for i in range(L+1)]
dp[0][0] = 0

for i,a in enumerate(A):
    cost_even = 2 if a==0 else a%2
    cost_odd = (a+1)%2

    dp[i+1][0] = min(dp[i+1][0], dp[i][0] + a)
    dp[i+1][1] = min(dp[i+1][1], dp[i][0] + cost_even)
    dp[i+1][2] = min(dp[i+1][2], dp[i][0] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][0] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][0] + a)

    dp[i+1][1] = min(dp[i+1][1], dp[i][1] + cost_even)
    dp[i+1][2] = min(dp[i+1][2], dp[i][1] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][1] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][1] + a)

    dp[i+1][2] = min(dp[i+1][2], dp[i][2] + cost_odd)
    dp[i+1][3] = min(dp[i+1][3], dp[i][2] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][2] + a)

    dp[i+1][3] = min(dp[i+1][3], dp[i][3] + cost_even)
    dp[i+1][4] = min(dp[i+1][4], dp[i][3] + a)

    dp[i+1][4] = min(dp[i+1][4], dp[i][4] + a)

print(min(dp[-1]))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]

INF = int(1e15)
DP = [[INF] * (n+1) for i in range(5)]
for i in range(4):
    DP[i][0] = 0

for i in range(n):
    DP[0][i+1] = DP[0][i] + A[i]
    DP[1][i+1] = min(DP[j][i] for j in range(2)) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2][i+1] = min(DP[j][i] for j in range(3)) + (A[i] + 1) % 2
    DP[3][i+1] = min(DP[j][i] for j in range(4)) + (A[i] % 2 if A[i] != 0 else 2)
    DP[4][i+1] = min(DP[j][i] for j in range(1, 5)) + A[i]

print(min(DP[i][n] for i in range(1, 5)))

Submission status: Accepted

Solution code:
n = int(input())
A = [int(input()) for i in range(n)]

INF = int(1e15)
DP = [[INF] * (n+1) for i in range(5)]
for i in range(4):
    DP[i][0] = 0

for i in range(n):
    DP[0][i+1] = DP[0][i] + A[i]
    DP[1][i+1] = min(DP[0][i], DP[1][i]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2][i+1] = min(DP[0][i], DP[1][i], DP[2][i]) + (A[i] + 1) % 2
    DP[3][i+1] = min(DP[0][i], DP[2][i], DP[3][i]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[4][i+1] = min(DP[2][i], DP[3][i], DP[4][i]) + A[i]

print(min(DP[i][n] for i in range(1, 5)))

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d
#2019-02-10

#DP

L = int(input())
A = [int(input()) for i in range(L)]

DP = [[float("inf") for i in range(5)] for j in range(L+1)]
for i in range(5):
    DP[0][i] = 0

def cost(s, i, A):
    if s == 0 or s == 4:
        return A[i]
    elif s == 1 or s == 3:
        if A[i] > 0:
            if A[i]%2 == 0:
                return 0
            else:
                return 1
        else:
            return 2
    else:
        if A[i]%2 == 1:
            return 0
        else:
            return 1

for i in range(L):
    for j in range(5):
        for k in range(j,5):
            DP[i+1][k] = min(DP[i+1][k], DP[i][j]+ cost(k, i, A))



print(min(DP[L]))

Submission status: Accepted

Solution code:
L = int(input())
a_list = [int(input()) for _ in range(L)]

dp = [[0] * 5 for _ in range(L+1)]

for i in range(L):
    a = a_list[i]

    if a > 0:
        even = a % 2
    else:
        even = 2
    odd = (a + 1) % 2

    # 0
    dp[i+1][0] = dp[i][0] + a
    # 0でない偶数
    dp[i + 1][1] = min(dp[i][0], dp[i][1]) + even
    # 奇数
    dp[i + 1][2] = min(dp[i][0], dp[i][1], dp[i][2]) + odd
    # 0でない偶数
    dp[i + 1][3] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) + even
    # 0
    dp[i + 1][4] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]) + a
print(min(dp[L]))

Submission status: Accepted

Solution code:
l = int(input())
a = []
for i in range(l):
  a.append(int(input()))
  
dp=[[0]*5 for i in range(l+1)]

for i in range(0,l):
  if a[i]==0:
    even=2
  else:
    even=a[i]%2
  
  dp[i+1][0]=dp[i][0]+a[i]
  dp[i+1][1]=min(dp[i][0],dp[i][1]) + even
  dp[i+1][2]=min(dp[i][0],dp[i][1],dp[i][2]) + (a[i]+1)%2
  dp[i+1][3]=min(dp[i][0],dp[i][1],dp[i][2],dp[i][3]) + even
  dp[i+1][4]=min(dp[i][0],dp[i][1],dp[i][2],dp[i][3],dp[i][4]) + a[i]
  
print(min(dp[l]))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for _ in range(L)]
dp = [[0]*5 for _ in range(L)]
dp[0][0] = A[0]
dp[0][1] = A[0] % 2 if A[0] > 0 else 2
dp[0][2] = 1-A[0] % 2
dp[0][3] = A[0] % 2 if A[0] > 0 else 2
dp[0][4] = A[0]
for i in range(1, L):
    dp[i][0] = dp[i-1][0] + A[i]
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][1] = min(dp[i-1][0], dp[i-1][1])+tmp
    tmp = 1-A[i] % 2
    dp[i][2] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2])+tmp
    tmp = A[i] % 2 if A[i] > 0 else 2
    dp[i][3] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3])+tmp
    dp[i][4] = min(dp[i-1][0], dp[i-1][1], dp[i-1]
                   [2], dp[i-1][3], dp[i-1][4]) + A[i]
print(min(dp[L-1]))

Submission status: Accepted

Solution code:
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[[0 for _ in range(5)] for _ in range(L+1)]

for i in range(1,L+1):
    a=A[i-1]
    back = a%2 if a>0 else 2
    through = (a+1)%2


    dp[i][0]=dp[i-1][0]+a
    dp[i][1]=min(dp[i-1][0:2])+back
    dp[i][2]=min(dp[i-1][0:3])+through
    dp[i][3]=min(dp[i-1][0:4])+back
    dp[i][4]=min(dp[i-1][0:5])+a

print(min(dp[L]))

Submission status: Accepted

Solution code:
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[0 for _ in range(5)]

for a in A:
    back = a%2 if a>0 else 2
    through = (a+1)%2

    dp[4] = min(dp[0:5]) + a
    dp[3] = min(dp[0:4]) + back
    dp[2] = min(dp[0:3]) + through
    dp[1] = min(dp[0:2]) + back
    dp[0] = dp[0]+a

print(min(dp))

Submission status: Accepted

Solution code:
L=int(input())
A=[int(input()) for _ in range(L)]
dp=[0 for _ in range(5)]

for i in range(1,L+1):
    a=A[i-1]
    back = a%2 if a>0 else 2
    through = (a+1)%2

    dp[4] = min(dp[0:5]) + a
    dp[3] = min(dp[0:4]) + back
    dp[2] = min(dp[0:3]) + through
    dp[1] = min(dp[0:2]) + back
    dp[0]=dp[0]+a

print(min(dp))

Submission status: Accepted

Solution code:
L=int(input())
A=[int(input()) for _ in range(L)]

INF=2*L

dp=[[INF for _ in range(5)] for _ in range(L+1)]

for j in range(5):
    dp[0][j]=0

for i in range(1,L+1):
    a=A[i-1]

    if A[i-1]==0:
        o=2
    else:
        o=A[i-1]%2

    e=(A[i-1]+1)%2


    dp[i][0]=dp[i-1][0]+a
    dp[i][1]=min(dp[i-1][0]+o,dp[i-1][1]+o)
    dp[i][2]=min(dp[i-1][0]+e,dp[i-1][1]+e,dp[i-1][2]+e)
    dp[i][3]=min(dp[i-1][0]+o,dp[i-1][1]+o,dp[i-1][2]+o,dp[i-1][3]+o)
    dp[i][4]=min(dp[i-1][0]+a,dp[i-1][1]+a,dp[i-1][2]+a,dp[i-1][3]+a,dp[i-1][4]+a)

print(min(dp[L]))

Submission status: Accepted

Solution code:
L = int(input())
A = [0]*L
for i in range(L):
    A[i] = int(input())
DP = [[float("inf")]*5 for i in range(L+1)]
DP[0][0] = 0
#DP[i][0]ではまだ0しか選んでいない状態。DP[i][2]では奇数まで選んでいる
for i in range(L):
    zero = A[i]
    if A[i] == 0:
        even = 2
        odd = 1
    elif A[i]%2==0:
        even = 0
        odd = 1
    else:
        even = 1
        odd = 0
    DP[i+1][0] = DP[i][0] + zero
    DP[i+1][1] = min(DP[i][0], DP[i][1]) + even
    DP[i+1][2] = min(DP[i][0], DP[i][1], DP[i][2]) + odd
    DP[i+1][3] = min(DP[i][0], DP[i][1], DP[i][2], DP[i][3]) + even
    DP[i+1][4] = min(DP[i][0], DP[i][1], DP[i][2], DP[i][3], DP[i][4]) + zero

print(min(DP[L][0], DP[L][1], DP[L][2], DP[L][3], DP[L][4]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    L = int(input())
    la = []
    for _ in range(L):
        la.append(int(input()))
    dp = [[0 for _ in range(5)] for _ in range(L+1)]

    for i in range(L):
        cost1 = la[i]
        cost2 = 2 if la[i] == 0 else la[i] % 2
        cost3 = 1 if la[i] == 0 else (la[i] + 1) % 2

        dp[i+1][0] = dp[i][0] + cost1
        dp[i+1][1] = min(dp[i][0], dp[i][1]) + cost2
        dp[i+1][2] = min(dp[i][0], dp[i][1], dp[i][2]) + cost3
        dp[i+1][3] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3]) + cost2
        dp[i+1][4] = min(dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4]) + cost1

    print(min(dp[L]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
L = int(input())
A = [int(input()) for _ in  range(L)]


DP = [0] * 5
for i in range(L):
    r0 = A[i]
    r1 = (A[i] + 1) % 2

    if A[i] == 0:
        r2 = 2
    else:
        r2 = A[i] % 2

    for i,r in zip(range(4,-1,-1), [r0,r2,r1,r2,r0]):
        DP[i] = min(DP[:i+1]) + r
        # print(DP)

print(min(DP))

Submission status: Accepted

Solution code:
def cost(place,zone):
    if zone == 0 or zone == 4:
        return A[place]
    elif zone == 1 or zone == 3:
        if A[place] == 0:
            return 2
        elif A[place] % 2 == 0:
            return 0
        else:
            return 1
    else:
        if A[place] % 2 == 0:
            return 1
        else:
            return 0

if __name__=='__main__':
    L = int(input())
    A = [int(input()) for i in range(L)]

    # dp配列の初期化
    dp = [[0 for _ in range(5)] for _ in range(L+10)]
    # 初項の設定
    for j in range(5):
        dp[0][j] = cost(0,j)
    # dp配列の更新
    for i in range(1,L):
        dp[i][0] = dp[i-1][0]+cost(i,0)
        for j in range(1,5):
            # 0〜jまでの最小に，i番目をjにするためのコストを足したものが最小
            dp[i][j] = min(min(dp[i-1][0:j+1])+cost(i,j),dp[i][j-1])
    # print(dp)
    print(min(dp[L-1]))

Submission status: Accepted

Solution code:
L = int(input())
A = [int(input()) for i in range(L)]

dp = [[0 for _ in range(5)] for _ in range(L)]

# print(dp)

def cost(place,zone):
    if zone == 0 or zone == 4:
        return A[place]
    elif zone == 1 or zone == 3:
        if A[place] == 0:
            return 2
        elif A[place] % 2 == 0:
            return 0
        else:
            return 1
    else:
        if A[place] % 2 == 0:
            return 1
        else:
            return 0

for j in range(5):
    dp[0][j] = cost(0,j)
# print(dp[0])

for i in range(L):
    for j in range(5):
        dp[i][j] = min(dp[i-1][0:j+1])+cost(i,j)
print(min(dp[L-1]))

Submission status: Accepted

Solution code:
L = int(input())
A_list = [0]*L
for i in range(L):
    A_list[i] = int(input())

DP = [0]*5
for i in range(L):
    # 全て
    r0 = A_list[i]
    # 通過する場合
    r1 = (A_list[i] + 1) % 2
    # 往復する場合
    if A_list[i] == 0:
        r2 = 2
    else:
        r2 = A_list[i] % 2
    
    DP[4] = min(DP[0], DP[1], DP[2], DP[3], DP[4]) + r0
    DP[3] = min(DP[0], DP[1], DP[2], DP[3]) + r2
    DP[2] = min(DP[0], DP[1], DP[2]) + r1
    DP[1] = min(DP[0], DP[1]) + r2
    DP[0] = DP[0] + r0
    
print(min(DP))

Submission status: Accepted

Solution code:
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    m = x % 2
    y = m + (not x) * 2
    z = 1 - m
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Submission status: Accepted

Solution code:
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    m = x % 2
    y = m + (x == 0) * 2
    z = 1 - m
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Submission status: Accepted

Solution code:
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    y = x % 2 + (x == 0) * 2
    z = (x + 1) % 2
    
    dp[i+1][0] = dp[i][0] + x
    dp[i+1][1] = min(dp[i][:2]) + y
    dp[i+1][2] = min(dp[i][:3]) + z
    dp[i+1][3] = min(dp[i][:4]) + y
    dp[i+1][4] = min(dp[i]) + x

print(min(dp[-1]))

Submission status: Accepted

Solution code:
a = [int(input()) for _ in range(int(input()))]

dp = [[0] * 5 for _ in range(len(a) + 1)]

for i, x in enumerate(a):
    y = x % 2 + (x == 0) * 2
    z = (x + 1) % 2
    
    dp[i+1][0] = min(dp[i][0:1]) + x
    dp[i+1][1] = min(dp[i][0:2]) + y
    dp[i+1][2] = min(dp[i][0:3]) + z
    dp[i+1][3] = min(dp[i][0:4]) + y
    dp[i+1][4] = min(dp[i][0:5]) + x

print(min(dp[-1]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

L = int(input())
A = [int(input()) for _ in range(L)]

DP = [0] * 5
#  ----- L ----- S ----- G ----- R -----
# |--0--| |--1--| |--2--| |--3--| |--4--|
# |--*--| |--偶--| |--奇--| |--偶--| |--*--|
for i in range(L):
    DP[4] = min(DP[0:5]) + A[i]
    DP[3] = min(DP[0:4]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[2] = min(DP[0:3]) + ((A[i] + 1) % 2)
    DP[1] = min(DP[0:2]) + (A[i] % 2 if A[i] != 0 else 2)
    DP[0] = DP[0] + A[i]

print(min(DP))

Submission status: Accepted

Solution code:
l = int(input())
a = [int(input()) for _ in range(l)]

ans = [[0] * 5 for _ in range(l + 1)]
for n in range(1, l + 1):
    c = a[n - 1]
    ans[n][0] = ans[n - 1][0] + c
    ans[n][1] = min(ans[n - 1][:2]) + (c % 2 if c > 0 else 2)
    ans[n][2] = min(ans[n - 1][:3]) + (c + 1) % 2
    ans[n][3] = min(ans[n - 1][:4]) + (c % 2 if c > 0 else 2)
    ans[n][4] = min(ans[n - 1][:5]) + c

print(min(ans[l]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def zr(x):
    return x


def ev(x):
    return x % 2 if x > 0 else 2


def od(x):
    return (x + 1) % 2 if x > 0 else 1


INF = 10**9 + 1

L = int(input())
A = [int(input()) for _ in range(L)]

dp = [[0] * 5] + [[INF] * 5 for _ in range(L)]
for i, x in enumerate(A):
    for t, f in enumerate([zr, ev, od, ev, zr]):
        dp[i + 1][t] = min(dp[i + 1][t], min(dp[i][:t + 1]) + f(x))

print(min(dp[L]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def f(x):
    return x % 2 if x > 0 else 2


def g(x):
    return (x - 1) % 2 if x > 0 else 1


INF = 10**9 + 1

L = int(input())
A = [int(input()) for _ in range(L)]

dp = [[0] * 5] + [[INF] * 5 for _ in range(L)]
for i in range(L):
    dp[i + 1][0] = min(dp[i + 1][0], min(dp[i][:1]) + A[i])
    dp[i + 1][1] = min(dp[i + 1][1], min(dp[i][:2]) + f(A[i]))
    dp[i + 1][2] = min(dp[i + 1][2], min(dp[i][:3]) + g(A[i]))
    dp[i + 1][3] = min(dp[i + 1][3], min(dp[i][:4]) + f(A[i]))
    dp[i + 1][4] = min(dp[i + 1][4], min(dp[i][:5]) + A[i])

print(min(dp[L]))

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(input()) for _ in range(n)]
def ear(n,t):
    if n:
        if t == 1 or t == 3:
            return n%2
        elif t == 2:
            return (n-1)%2
        else:
            return n
    else:
        if t == 1 or t == 3:
            return 2
        elif t == 2:
            return 1
        else:
            return 0
dp = [[0]*5 for _ in range(n)]
for i in range(n):
    for t in range(5):
        if i == 0:
            dp[i][t] = ear(arr[i],t)
        else:
            if t == 0:
                mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            else:
                if mind > dp[i-1][t]:
                    mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            dp[i][t] = ear(arr[i],t) + mind
print(min(dp[n-1]))

Submission status: Accepted

Solution code:
L = int(input())

inf = float('inf')
dp = [[inf] * 5 for _ in range(L+1)]
dp[0][0] = 0
for i in range(1, L+1):
    a = int(input())

    b = a & 1
    c = b ^ 1
    p, n = dp[i-1], dp[i]
    n[0] = p[0] + a
    n[1] = min(p[:2]) + b
    n[2] = min(p[:3]) + c
    n[3] = min(p[:4]) + b
    n[4] = min(p[:5]) + a

    if a == 0:
        n[1] += 2
        n[3] += 2

print(min(dp[L]))

Submission status: Accepted

Solution code:
l=int(input())
A=[int(input()) for _ in range(l)]

def even(n):
    if n==0:
        return 2
    else:
        return n%2
def odd(n):
    return (n+1)%2

DP=[[0]*5 for _ in range(l)]
DP[0]=[A[0],even(A[0]),odd(A[0]),even(A[0]),A[0]]
for i in range(1,l):
    DP[i][0]=DP[i-1][0]+A[i]
    DP[i][1]=min(DP[i-1][:2])+even(A[i])
    DP[i][2]=min(DP[i-1][:3])+odd(A[i])
    DP[i][3]=min(DP[i-1][:4])+even(A[i])
    DP[i][4]=min(DP[i-1])+A[i]
print(min(DP[l-1]))

Submission status: Accepted

Solution code:
l = int(input())
a = [int(input()) for _ in range(l)]

INF = float('inf')
dp = [[INF] * 5 for _ in range(l+10)]
dp[0][0] = 0

for i in range(l):
    for j in range(4):
        dp[i][j+1] = min(dp[i][j+1], dp[i][j])

    dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + a[i])
    dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + a[i] % 2 if a[i] > 0 else dp[i][1] + 2)
    dp[i + 1][2] = min(dp[i + 1][2], dp[i][2] + (a[i] + 1) % 2)
    dp[i + 1][3] = min(dp[i + 1][3], dp[i][3] + a[i] % 2 if a[i] > 0 else dp[i][3] + 2)
    dp[i + 1][4] = min(dp[i + 1][4], dp[i][4] + a[i])

ans = float('inf')
for j in range(5):
    ans = min(ans, dp[l][j])

print(ans)

Submission status: Accepted

Solution code:
l = int(input())
a = [int(input()) for _ in range(l)]

dp = [[0]*5 for _ in range(l)]

if a[0] == 0:
    dp[0] = [a[0],2,1,2,a[0]]
elif a[0]%2 == 0:
    dp[0] = [a[0],0,1,0,a[0]]
else:
    dp[0] = [a[0],1,0,1,a[0]]

for i in range(1,l):
    dp[i][0] = dp[i-1][0]+a[i]
    dp[i][2] = min(dp[i-1][0:3])+1-a[i]%2
    dp[i][4] = min(dp[i-1][0:5])+a[i]
    if a[i]!=0:
        dp[i][3] = min(dp[i-1][0:4])+a[i]%2
        dp[i][1] = min(dp[i-1][0], dp[i-1][1])+a[i]%2
    else:
        dp[i][3] = min(dp[i-1][0:4])+2
        dp[i][1] = min(dp[i-1][0], dp[i-1][1])+2

print(min(dp[l-1]))

Submission status: Accepted

Solution code:
l=int(input())
a=[int(input()) for x in range(l)]
def ds_tu(i):
    if a[i]==0:return 2
    return a[i]%2
ans=[[0 for i in range(5)] for j in range(l)]
ans[0][0]=a[0]
ans[0][1]=ds_tu(0)
ans[0][2]=(a[0]+1)%2
ans[0][3]=ds_tu(0)
ans[0][4]=a[0]
for i in range(1,l):
    ans[i][0]=ans[i-1][0]+a[i]
    ans[i][1]=min(ans[i-1][0:2])+ds_tu(i)
    ans[i][2]=min(ans[i-1][0:3])+(a[i]+1)%2
    ans[i][3]=min(ans[i-1][0:4])+ds_tu(i)
    ans[i][4]=min(ans[i-1])+a[i]
    
print(min(ans[l-1]))

Submission status: Accepted

Solution code:
L = int(input())
A = [0] * (L + 1)
DP = [[0, 0, 0, 0, 0] for i in range(L + 1)]
for i in range(L):
  a = int(input())
  DP[i + 1][0] = DP[i][0] + a
  DP[i + 1][1] = min(min(DP[i][:2]), DP[i + 1][0]) + (a % 2 if a else 2)
  DP[i + 1][2] = min(min(DP[i][:3]), DP[i + 1][1]) + ((1 - a % 2) if a else 1)
  DP[i + 1][3] = min(min(DP[i][:4]), DP[i + 1][2]) + (a % 2 if a else 2)
  DP[i + 1][4] = min(min(DP[i]), DP[i + 1][3]) + a
print(min(DP[L]))