baekjun 11066. 파일 합치기

 knuth's optimization을 공부해야함

#include <iostream>
#include <algorithm>
 
#define MAX    0x12345678
 
using namespace std;
int files[501];
int dp[501][501];
int pSum[501];
int n;
 
// iteration
// dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + pSum[j] - pSum[i - 1]); (i<=k<j)
void combineFile() {
    for (int d = 1; d < n; d++) {
        for (int tx = 1; tx + d <= n; tx++) {
            int ty = tx + d; // ty <= n
            dp[tx][ty] = MAX;
            for (int mid = tx; mid < ty; mid++) {
                dp[tx][ty] = min(dp[tx][ty], dp[tx][mid] + dp[mid + 1][ty] + pSum[ty] - pSum[tx - 1]);
            }
        }
    }
}
 
int combineFile2(int tx, int ty) {
    if (dp[tx][ty] != MAX) {
        return dp[tx][ty];
    }
    if (tx == ty) {
        return dp[tx][ty] = 0;
    }
    if (tx + 1 == ty) {
        return dp[tx][ty] = files[tx] + files[ty];
    }
    for (int mid = tx; mid < ty; mid++) {
        int left = combineFile2(tx, mid);
        int right = combineFile2(mid + 1, ty);
        dp[tx][ty] = min(dp[tx][ty], left + right);
    }
    return dp[tx][ty] += pSum[ty] - pSum[tx - 1];
}
 
int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> files[i];
            pSum[i] = pSum[i - 1] + files[i];
        }
        // combineFile();
 
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = MAX;
            }
        }
        cout << combineFile2(1, n) << endl;
    }
    //system("pause");
    return 0;
}

18 nov 2

D[i][j] = D[i][k] + D[k+1][j] + pSum[j] - pSum[i] (i <= k < j)

#include <iostream>
#include <cstring>
using namespace std;
 
int files[501];
int cache[501][501];
int pSum[501];
 
int fc(int i, int j){
    if(i == j){
        return 0;
    }
    if(cache[i][j]!= -1){
        return cache[i][j];
    }
    int & ret = cache[i][j];
    for(int k = i; k < j; k++){
        int tmp = fc(i, k) + fc(k + 1, j) + pSum[j] - pSum[i-1];
        if(ret == -1 || ret > tmp){
            ret = tmp;
        }
    }
    return ret;
}
 
int main(){
    int cases;
    cin >> cases;
    while(cases--){
        int N;
        cin >> N;
        memset(cache, -1, sizeof(cache));
        memset(pSum, 0, sizeof(pSum));
        for(int i = 1; i <= N; i++){
            cin >> files[i];
            pSum[i] = pSum[i - 1] + files[i];
        }
        cout << fc(1, N);
    }
    return 0;
}