파일 합치기 2 C++ - 백준 13974

https://www.acmicpc.net/problem/13974

DP 문제.

파일 합치기와는 달리 $O(n^3)$ DP로는 TLE를 받는다.

따라서 크누스 최적화를 사용해 $O(n^2)$에 통과시켜야 한다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int t,n;
ll a[5000],dp[5000][5000],cur;
int opt[5000][5000];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    for(int i=0;i<5000;i++) opt[i][i]=i;
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> a[i];
            if(i!=0) a[i]+=a[i-1];
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<n-i;j++){
                dp[j][i+j]=dp[j][opt[j][i+j-1]]+dp[opt[j][i+j-1]+1][i+j]+a[i+j]-(j!=0?a[j-1]:0);
                opt[j][i+j]=opt[j][i+j-1];
                for(int k=opt[j][i+j-1]+1;k<=opt[j+1][i+j];k++){
                    cur=dp[j][k]+dp[k+1][i+j]+a[i+j]-(j!=0?a[j-1]:0);
                    if(dp[j][i+j]>cur){
                        dp[j][i+j]=cur;
                        opt[j][i+j]=k;
                    }
                }
            }
        }
        cout << dp[0][n-1] << '\n';    
    }
    return 0;
}