Problem:


E : Sigma / Σ

Problem

小学生のづあい君は同じ足し算にも得意不得意があり、 0 以上の整数 X, Y に対して、X + Y を計算するのにかかる時間(秒)が次のように決まる。

1 の位から順番に計算していく。

10 進数表記で 10i 位の計算には xi × yi + ci 秒かかる。

  
xi は X の10進数表記で 10i の位の数である。

  
yi は Y の10進数表記で 10i の位の数である。

  
ただし i が X の桁数より大きくなる時は xi = 0 とする。Y についても同様である。

  
ci は、 i = 0 または xi-1 + yi-1 + ci-1 < 10 ならば 0、 そうでなければ 1 である。

0 以上の整数 i についての xi × yi + ci の総和が X + Y の計算にかかる時間である。

ある日、づあい君の先生は長さ N の整数列 a0, ... , aN-1 の和を計算する宿題を出した。づあい君は数列の順番を並び替えることはできないが、足し算の式に括弧を付けることにより、足し算の順番を自由に変えることができる。例えば N = 4 の場合、順番は次の 5 通りある。

  
((a0 + a1) + a2) + a3

  
(a0 + a1) + (a2 + a3)

  
(a0 + (a1 + a2)) + a3

  
a0 + ((a1 + a2) + a3)

  
a0 + (a1 + (a2 + a3))

それぞれの括弧 (x + y) の中で上で説明した時間がかかるとすると、総和を求めるのにかかる時間は最小で何秒になるだろうか。

Input

入力は次のような形式で与えられる。

N
a0 a1 ... aN-1

Constraints

入力はすべて整数である。

2 ≦ N ≦ 300

0 ≦ ai ≦ 1,000,000

Output

答えの秒数を1行で出力せよ。

Samples

Sample Input 1

3
1 2 3

Sample Output 1

11

次のように計算すると最も速い。

2 + 3 = 5 ( 2 × 3 = 6 秒かかる)

1 + 5 = 6 ( 1 × 5 = 5 秒かかる)



Sample input:
3
1 2 3


Sample output:
11

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
inf = float("INF")
dp = [[inf] * (n + 1) for _ in range(n)]
for i in range(n - 1): a[i + 1] += a[i]
a.insert(0, 0)
f = [[0] * (n + 1) for i in range(n)]
for i in range(n):
    fi = f[i]
    for k in range(i + 1, n + 1):
        fi[k] = a[k]-a[i]
def time(l, m, r, res, x, fl):
    sumlm = fl[m]
    summr = f[m][r]
    c = 0
    while sumlm or summr or c:
        lm = sumlm % 10
        mr = summr % 10
        res += lm * mr + c
        if res >= x:
            return x
        c =  (lm + mr + c > 9)
        sumlm //= 10
        summr //= 10
    return res
for i in range(n):
    dp[i][i + 1] = 0

for Ra in range(1,n+1):
    for l in range(n-Ra+1):
        r = l+Ra
        dpl = dp[l]
        x = dpl[r]
        fl = f[l]
        for m in range(l+1, r):
            x = time(l, m, r,dpl[m] + dp[m][r], x, fl)
        dpl[r] = x

print(dp[0][n])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
def calc(l,m,r,f,dp):
    a = f[l][m]
    b = f[m][r]
    res = dp[l][m]+dp[m][r]
    c = 0
    while a or b or c:
        a0 = a%10
        b0 = b%10
        res += a0*b0+c
        if res >= dp[l][r]:
            return dp[l][r]
        c = (a0+b0+c >= 10)
        a //= 10
        b //= 10
    return res

def solve():
    n = int(sys.stdin.readline())
    a = [int(x) for x in sys.stdin.readline().split()]
    dp = [[float("inf")]*(n+1) for i in range(n)]
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    f = [[0]*(n+1) for i in range(n)]
    for l in range(n):
        dp[l][l+1] = 0
        for r in range(l+1,n+1):
            f[l][r] = a[r]-a[l]
    for le in range(2,n+1):
        for l in range(n-le+1):
            r = l+le
            for m in range(l+1,r):
                dp[l][r] = calc(l,m,r,f,dp)
                
    print(dp[0][n])

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from itertools import accumulate

def main():
  n = int(input())
  alst = list(map(int, input().split()))
  acc = [0] + list(accumulate(alst))

  INF = 10 ** 10
  dp = [[None] * n for _ in range(n)]
  for i in range(n):dp[i][i] = 0
    
  for length in range(2, n + 1):
    for left in range(n - length + 1):
      right = left + length - 1
      min_score = INF
      to_right = acc[right + 1]
      to_left = acc[left]
      for k in range(left, right):
        left_sum = acc[k + 1] - to_left
        right_sum = to_right - acc[k + 1]
        score = dp[left][k] + dp[k + 1][right]
        c = 0
        while left_sum or right_sum or c:
          x = left_sum % 10
          y = right_sum % 10
          score += x * y + c
          if min_score <= score:break
          c = 0 if  x + y + c < 10 else 1
          left_sum //= 10
          right_sum //= 10
        else:
          min_score = score
      dp[left][right] = min_score
  print(dp[0][n - 1])

main()