[BOJ/백준] 13974 파일 합치기 2

import sys
input = sys.stdin.readline
 
T = int(input())
 
INF = 10**9
for _ in range(T):
    N = int(input())
    books = list(map(int,input().split()))
    prefix_sum = [0]*(N+1)
    dp =[[10**9] *N for _ in range(N)]
    min_k_store_array = list(range(N))
    for i in range(N):
        dp[i][i] = 0
        prefix_sum[i+1] = prefix_sum[i] + books[i]
    for term in range(1,N):
        new_arr = [None]*N
        for i in range(N-term):
            j = term+i
            for k in range(min_k_store_array[i],min(min_k_store_array[i+1]+1,j)):
                if dp[i][j] > dp[i][k]+dp[k+1][j]:
                    dp[i][j] = dp[i][k]+dp[k+1][j]
                    new_arr[i] = k
 
            dp[i][j] += prefix_sum[j+1] - prefix_sum[i]
        min_k_store_array = new_arr
    print(dp[0][N-1])

 

 

 

T = int(input())
INF = float('inf')
 
for _ in range(T):
    N = int(input())
    arr = list(map(int,input().split()))
    result = 0
    while len(arr) >=2:
        find_idx = len(arr)-2
        for i in range(len(arr)-2):
            if arr[i] <= arr[i+2]:
                find_idx = i
                break
        a1 = arr.pop(find_idx)
        a2 = arr.pop(find_idx)
        B = a1 + a2
        arr.insert(find_idx,B)
        result += B
        B_index = find_idx
        while B_index >0 and arr[B_index-1] < arr[B_index]:
            arr[B_index],arr[B_index-1] = arr[B_index-1],arr[B_index]
            B_index -= 1
 
    print(result)