단계적으로 최소비용을 구해나간다는 문제의 서술로부터 다이나믹 프로그래밍을 떠올릴 수 있었습니다.

$C(i, j)$를 인덱스 $i$부터 $j$까지 파일을 합하는 최소 비용이라 정의하면,

$$C(i, j) = \min_{i \le k \lt j}[C(i, k) + C(k + 1, j)] + \sum_{n = i}^{j} \mathrm{Size}[n]$$

$\mathrm{Size}[i..j]$는 부분합을 이용해 $O(1)$만에 구할 수 있으므로 전체 시간복잡도는 $O(K^3)$이 됩니다.

코드 
use std::fmt::Write;
use std::io::{stdin, Read};

fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut output = String::new();
    let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
    let t = input.next().unwrap();
    for _ in 0..t {
        let k = input.next().unwrap();
        let mut sum = vec![0];
        sum.extend(input.by_ref().take(k).scan(0, |state, x| {
            *state += x;
            Some(*state)
        }));
        let mut min_cost = Matrix(vec![0; k * k], k);
        for gap in 1..k {
            for i in 0..k - gap {
                let mut min = usize::MAX;
                for j in i..i + gap {
                    min = min.min(min_cost[i][j] + min_cost[j + 1][i + gap]);
                }
                min_cost[i][i + gap] = min + sum[i + gap + 1] - sum[i];
            }
        }
        writeln!(output, "{}", min_cost[0][k - 1]).ok();
    }
    print!("{}", output);
}

struct Matrix<T>(Vec<T>, usize);

impl<T> std::ops::Index<usize> for Matrix<T> {
    type Output = [T];
    fn index(&self, index: usize) -> &Self::Output {
        &self.0[index * self.1..][..self.1]
    }
}

impl<T> std::ops::IndexMut<usize> for Matrix<T> {
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        &mut self.0[index * self.1..][..self.1]
    }
}