Problem:


お菓子の分割
　

  問題

長さ N ミリメートルの棒状のお菓子が 1 本ある(ここで N は偶数). 2 人の JOI
関係者が,このお菓子を複数本に切断して,合計 N/2 ミリメートルずつに分けること
にした.

理由は不明であるが,このお菓子は場所によって切断のしやすさが異なっている.
2 人は,お菓子を左から 1 ミリメートルごとに調べ,各場所で切断に何秒かかるか
を割り出した.2 人がお菓子を分けるための切断にかかる秒数の最小値を求めるプ
ログラムを作成せよ.

入力

入力の 1 行目には,棒の長さ N(2 ≤ N ≤ 10000 ,ただし N は偶数) が書かれてい
る.入力の i + 1 行目 (1 ≤ i ≤ N − 1) には,左端から i ミリメートル目の場所の切
断にかかる秒数を表す整数 ti (1 ≤ ti ≤ 10000) が書かれている.切断可能な場所が
N − 1 箇所であることに注意せよ.

採点用データのうち,配点の 5% 分については,高々 2 カ所を切断することで最
小値を実現でき,10% 分については,高々 3 カ所を切断することで最小値を実現で
きる.配点の 20% 分については,N ≤ 20 である.

 出力

出力は2 人がお菓子を分るための切断にかかる秒数の最小値を含む 1 行からなる.

 入出力例

入力例 1
  

6
1
8
12
6
2

出力例 1

7

この場合,左端から 1 ミリメートルと 4 ミリメートルの場所で切断するとかかる
秒数が最小となる.かかる秒数は 1 秒と 6 秒で,合計 7 秒である.

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
6
1
8
12
6
2


Sample output:
7

Submission status: Memory Limit Exceeded

Solution code:
INF = 100000000
n = int(input())
l = [0 if i == 0 else int(input()) for i in range(n)]
dp = [[[INF] * 2 for i in range(n // 2 + 1)] for j in range(n + 1)]

dp[1][1][0] = 0
dp[1][0][1] = 0

for i in range(2,n + 1):
  for j in range(1,n // 2 + 1):
    dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + l[i - 1])
    dp[i][j][1] = min(dp[i - 1][j][1], dp[i - 1][j][0] + l[i - 1])
print(min(dp[n][n//2][0], dp[n][n//2][1]))

Submission status: Accepted

Solution code:
INF = 1<<31
n = input()
dp = [[[INF]*2 for _ in xrange(n/2+2)] for _ in range(2)]
dp[1][1][0] = dp[1][0][1] = 0
for i in range(2,n+1):
    x = i % 2
    s = input()
    t = min(i,n/2)
    for j in range(1,t+1):
        dp[x][j][0] = min(dp[1-x][j-1][0], dp[1-x][j-1][1] + s)
        dp[x][j][1] = min(dp[1-x][j][0] + s, dp[1-x][j][1])
print min(dp[0][n/2])

Submission status: Accepted

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        if dp[j]>dp[i-j]+a:dp[j]=dp[i-j]+a
        if dp[i-j]>dp[j]+a:dp[i-j]=dp[j]+a
print(dp[n//2])

Submission status: Accepted

Solution code:

n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
cost = [int(input()) for _ in range(n-1)]
for i in range(1,n):
    for j in range(i):
        if dp[i-j]+cost[i-1] < dp[j]: dp[j] = dp[i-j]+cost[i-1]# = min(dp[j],dp[i-j]+cost[i-1])
        if dp[j]+cost[i-1] < dp[i-j]: dp[i-j] = dp[j]+cost[i-1]# = min(dp[i-j],dp[j]+cost[i-1])
    #print(dp)
print(dp[n//2])

Submission status: Accepted

Solution code:
# AOJ 0550: Dividing Snacks
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

INF = 0x7fffffff

n = int(input())
dp = [INF]*(n+1)
dp[0] = 0
for i in range(1, n):
	t = int(input())
	for j in range(1+(i>>1)):
		if dp[j] > dp[i-j] + t: dp[j] = dp[i-j] + t;
		if dp[i-j] > dp[j] + t: dp[i-j] = dp[j] + t
print(dp[n>>1])

Submission status: Accepted

Solution code:
#お菓子
n = int(input())
times = [int(input()) for _ in range(n-1)]
dp = [10**20 for i in range(n+1)]
dp[0] = 0

for i in range(1,n):
    for j in range(i):
        if dp[j] > dp[i-j] + times[i-1]: 
          dp[j] = dp[i-j] + times[i-1]

        if dp[i-j] > dp[j] + times[i-1]: 
          dp[i-j] = dp[j] + times[i-1]

print(dp[n//2])

Submission status: Output Limit Exceeded

Solution code:
n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
for i in range(1,n):
    cost = int(input())
    for j in range(i):
        dp[j] = min(dp[j],dp[i-j]+cost)
        dp[i-j] = min(dp[j]+cost,dp[i-j])
    print(dp)
print(dp[n//2])

Submission status: Runtime Error

Solution code:
while True:
  pass

Submission status: Runtime Error

Solution code:
n = input()
l = [input() for i in range(n-1)]
dp = [[n*n]*2 for i in range(n+1)]
dp[1][0] = 0
for i in range(1,n):
    for j in range(i+1,0,-1):
        dp[j][1] = min(dp[j][1], dp[j][0]+l[i-1])
        dp[j][0] = min(dp[j-1][0], dp[j-1][1]+l[i-1])
print min(dp[n/2])

Submission status: Runtime Error

Solution code:
INF = 1<<31
n = input()
l = [input() for i in range(n-1)]
dp = [[INF]*2 for i in range(n+1)]
dp[1][0] = 0
for i in range(1,n):
    for j in range(i+1,0,-1):
        dp[j][1] = min(dp[j][1], dp[j][0]+l[i-1])
        dp[j][0] = min(dp[j-1][0], dp[j-1][1]+l[i-1])
print min(dp[n/2])

Submission status: Runtime Error

Solution code:
INF = 1<<31
n = input()
l = [input() for i in xrange(n-1)]
dp = [[INF]*2 for i in xrange(n+1)]
dp[1][0] = 0
for i in xrange(1,n):
    for j in xrange(i+1,0,-1):
        dp[j][1] = min(dp[j][1], dp[j][0]+l[i-1])
        dp[j][0] = min(dp[j-1][0], dp[j-1][1]+l[i-1])
print min(dp[n/2])

Submission status: Runtime Error

Solution code:
INF = 1<<31
n = input()
l = [0]*(n+1)
for i in xrange(1,n):
    l[i] = input()
dp = [[INF]*2 for i in xrange(n+1)]
dp[1][0] = 0
for i in xrange(1,n):
    for j in xrange(i+1,0,-1):
        dp[j][1] = min(dp[j][1], dp[j][0]+l[i])
        dp[j][0] = min(dp[j-1][0], dp[j-1][1]+l[i])
print min(dp[n/2])

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n+1):
    a=int(input())
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    try:a=int(input())
    except:break
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n+1):
    try:a=int(input())
    except:break
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
import sys
dp=[0]+[1<<20]*10000
n=int(input())
a=list(map(int,sys.stdin.readlines()))
for i in range(1,len(a)):
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a[i-1]),(dp[i-j],dp[j]+a[i-1])])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
import sys
dp=[0]+[1<<20]*10000
n=int(input())
a=list(map(int,sys.stdin.readlines()))
for i in range(1,n):
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a[i-1]),(dp[i-j],dp[j]+a[i-1])])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
#???????????±???????????\????????°????????£?????????????
import sys
dp = [0] + [1 << 20] * 10000
n = int(input())
a = list(map(int, sys.stdin.readlines()))
if len(a)==n:a.pop()
for i in range(1, n) :
	for j in range(i//2+1):
		dp[j], dp[i - j] = map(min, [(dp[j], dp[i - j] + a[i - 1]), (dp[i - j], dp[j] + a[i - 1])])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])
try:raise RuntimeError
except:exit()

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
for i in range(1,n):
    a=int(input())
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])
exit()

Submission status: Runtime Error

Solution code:
dp=[0]+[1<<20]*10000
n=int(input())
c=0
for i in range(1,n):
    if c==n-1:break
    a=int(input())
    c+=1
    for j in range(i//2+1):
        dp[j],dp[i-j]=map(min,[(dp[j],dp[i-j]+a),(dp[i-j],dp[j]+a)])
print(dp[n//2])

Submission status: Runtime Error

Solution code:
n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
for i in range(1,n):
    cost = int(input())
    for j in range(i):
        dp[j] = min(dp[j],dp[i-j]+cost)
        dp[i-j] = min(dp[j]+cost,dp[i-j])
    #print(dp)
print(dp[n//2])

Submission status: Runtime Error

Solution code:
INF = 100
n = int(input())
l = [0 if i == 0 else int(input()) for i in range(n)]
#dp = [[[INF] * 2 for i in range(n // 2 + 1)] for j in range(n + 1)]
#
#dp[1][1][0] = 0
#dp[1][0][1] = 0
#
#for i in range(2,n + 1):
#  for j in range(1,n // 2 + 1):
#    dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + l[i - 1])
#    dp[i][j][1] = min(dp[i - 1][j][1], dp[i - 1][j][0] + l[i - 1])
#print(min(dp[n][n//2][0], dp[n][n//2][1]))
#
dp = [[INF] * 2 for i in range(n // 2 + 1)]
dp[1][0] = 0
dp[0][1] = 0

for i in range(2, n + 1):
  for j in range(n // 2, -1, -1):
    a = min(dp[j - 1][0], dp[j - 1][1] + l[i - 1])
    b = min(dp[j][1], dp[j][0] + l[i - 1])
    dp[j][0] = a
    dp[j][1] = b
print(max(dp[n//2][0], dp[n//2][1]))