기본적인 동적계획법 접근은 dp[i][j]를 마지막 분할 지점이 i, 이전 분할 지점이 j일 때의 최소 비용으로 정의한다. 누적합을 sum[i] = Σk=1i a[k]로 두면, 전이식은 다음과 같다:

dp[i][j] = min{ dp[j][k] + (sum[i] - sum[j])² }   ( sum[i] - sum[j] ≥ sum[j] - sum[k] )

조건를 정리하면 sum[k] ≥ 2×sum[j] - sum[i]가 되며, 고정된 j에 대해 i가 증가함에 따라 하한선이 감소한다. 따라서 각 j에 대해 가능한 k의 범위를 추적하면서, 그 범위 내에서 dp[j][k]의 최솟값을 유지하는 방식으로 처리할 수 있다. 이를 위해 j마다 현재 가능한 최소값과 유효한 k의 범위를 관리하며, 전체 시간복잡도는 O(n²)로 떨어진다.

이러한 구현은 다음과 같이 가능하다:

for (int i = 1; i <= n; ++i) {
    dp[i][0] = sum[i] * sum[i];
    p[i] = i - 1;
    mx[i] = LLONG_MAX;
}

for (int i = 2; i <= n; ++i) {
    for (int j = 1; j < i; ++j) {
        while (p[j] >= 0 && sum[p[j]] >= 2 * sum[j] - sum[i]) {
            mx[j] = min(mx[j], dp[j][p[j]]);
            --p[j];
        }
        if (p[j] < j - 1) ++p[j];
        if (mx[j] != LLONG_MAX)
            dp[i][j] = mx[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]);
    }
}

long long ans = LLONG_MAX;
for (int i = 0; i < n; ++i)
    ans = min(ans, dp[n][i]);

printf("%lld\n", ans);

하지만 위 방법은 상태 압축이 불가능해 효율성이 제한된다. 그러나 문제의 조건을 만족하기 위해 상태를 축약할 수 없다. 대신, 결정 전이 테이블 기법을 활용할 수 있다. 중요한 관찰은, 각 전이에서 가능한 최대 k를 선택하면 더 나은 결과를 얻는다는 점이다. 또한 j가 클수록 dp[i][j] 값이 커지므로, 가능한 한 작은 마지막 구간을 선택하는 것이 유리하다.

왜냐하면 (a+b)² > a² + b²이므로, 더 많은 분할을 통해 총 제곱합을 줄일 수 있으며, 이는 후속 전이에도 유리한 조건을 제공한다. 따라서 최적 전이는 항상 가능한 가장 작은 마지막 구간을 선택하는 것이다.

이에 따라 새로운 상태 정의: dp[i]는 i까지의 분할에서의 최소 비용, p[i]는 i가 어디서 전이된지를 저장한다. 전이 조건은 sum[i] ≥ 2×sum[j] - sum[p[j]]이며, 이는 j에 대해 2×sum[j] - sum[p[j]] 값이 단조 증가하도록 유지하면, 이분 탐색 또는 큐를 이용한 선형 처리가 가능하다.

특히, sum[i]는 증가하므로, 이전에 유효했던 j는 계속 유효하다. 따라서 단조 큐(Monotonic Queue)를 사용하여, 2×sum[j] - sum[p[j]] 값이 오름차순이 되도록 유지한다. 새 원소를 추가할 때는 큐의 끝에서부터 조건을 만족하지 않는 원소를 제거하고, 이후 i에 대해 해당 조건을 만족하는 가장 오른쪽의 위치를 찾는다.

최종 구현은 다음과 같다:

dp[1] = a[1] * a[1];
int h = 1, t = 2;
q[1] = 0;
q[2] = 1;

for (int i = 2; i <= n; ++i) {
    // 현재 위치에서 가능한 최대 j 찾기
    while (h <= t && 2 * sum[q[h]] - sum[p[q[h]]] <= sum[i])
        ++h;
    --h;
    p[i] = q[h];

    dp[i] = dp[p[i]] + (sum[i] - sum[p[i]]) * (sum[i] - sum[p[i]]);

    // 큐의 끝에서 조건 만족하지 않는 원소 제거
    while (h <= t && 2 * sum[i] - sum[p[i]] <= 2 * sum[q[t]] - sum[p[q[t]]])
        --t;
    q[++t] = i;
}

printf("%lld\n", dp[n]);

마지막 12점은 큰 수 연산을 필요로 한다. 하지만 실제 계산 과정에서는 dp 배열 자체를 저장할 필요 없이, 전이 경로 p[i]만 저장하면 된다. 최종 결과는 p[n]에서 시작해 역추적하며 각 구간의 합을 제곱해서 누적하면 된다. 고정밀도 연산 구현은 복잡하므로 생략한다.