WIKIOI 2298 石子合并, http://www.wikioi.com/problem/2298/ POJ 1738 An old Stone Game, http://poj.org/problem?id=1738

stone_merge.c

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

int N;  /** 石头堆的个数. */
int *p;  /** 第i堆石头的个数p[i]. */
int **d;  /** 状态，d[i][j]表示合并第i堆到第j堆之间的石头的最小得分. */
int *S;  /** S[i]表示从第0堆到第i堆的石头总数. */


void dp() {
    int i, j, k, l; /* l表示区间长度 */

    /* 初始化 d */
    d[0][1] = p[0] + p[1];
    d[N-1][N-2] = p[N-1] + p[N-2];

    for (i = 1; i < N - 1; ++i) {
        d[i][i-1] = p[i-1] + p[i];
        d[i][i+1] = p[i] + p[i+1];
    }

    /* 初始化 S */
    S[0] = p[0];
    for (i = 1; i < N; i++) {
        S[i] = S[i-1] + p[i];
    }

    for (l = 2; l <= N; ++l) {
        for (i = 0; i <= N - l; ++i) {
            j = i + l -1;
            d[i][j] = INT_MAX;
            for (k = i; k < j; ++k) {
                /* 第i堆到第j堆的石头总数 */
                const int sum = S[j] - (i > 0 ? S[i - 1] : 0);
                if (d[i][j] > d[i][k] + d[k+1][j] + sum) {
                    d[i][j] = d[i][k] + d[k+1][j] + sum;
                }
            }
        }
    }
}

int main() {
    int i;
    scanf("%d", &N);
    p = (int*)calloc(N, sizeof(int));
    d = (int**)calloc(N, sizeof(int*));
    for (i = 0; i < N; i++) {
        d[i] = (int*)calloc(N, sizeof(int));
    }
    S = (int*)calloc(N, sizeof(int));

    for (i = 0; i < N; i++) {
        scanf("%d", &p[i]);
    }

    dp();
    printf("%d\n", d[0][N-1]);

    free(p);
    for (i = 0; i < N; i++) {
        free(d[i]);
    }
    free(d);
    free(S);
    return 0;
}