wikioi 1154, 能量项链, http://www.wikioi.com/problem/1154

energe_necklace.c

/* wikioi 1154, 能量项链, http://www.wikioi.com/problem/1154 */
#include <stdio.h>
#include <memory.h>
#include <limits.h>

#define MAXN 101

int N;  /** 矩阵的个数. */
int a[MAXN];
int p[MAXN];  /** 矩阵Ai的维度是p[i-1]xp[i]. */
int d[MAXN][MAXN];  /** 状态，d[i][j]表示子问题Ai~Aj 的最优解. */
int s[MAXN][MAXN]; /** 子问题Ai~Aj 应该在s[i][j]处断开 */

/**
 * @brief 打印子问题Ai~Aj的解
 * @param[in] i Ai
 * @param[in] j Aj
 * @return 无
 */
void print(const int i, const int j) {
    if (i == j) {
        printf("A%d",i);
    } else {  /* i < j */
        printf("(");
        print(i, s[i][j]);
        printf(" x ");
        print(s[i][j]+1, j);
        printf(")");
    }
}

void dp() {
    int i, j, k, l; /* l表示区间长度 */
    //for (i = 1;i <= N; ++i) d[i][i]=0;
    memset(d, 0, sizeof(d));

    for (l = 2; l <= N; ++l) {
        for (i = 1; i <= N - l + 1; ++i) {
            j = i + l -1;
            d[i][j] = INT_MIN;
            for (k = i; k < j; ++k) {
                /* 大于号改为小于号 */
                if (d[i][j] < d[i][k] + d[k+1][j] + p[i-1] * p[k] * p[j]) {
                    d[i][j] = d[i][k] + d[k+1][j] + p[i-1] * p[k] * p[j];
                    s[i][j] = k;
                }
            }
        }
    }
}

int main() {
    int i, j;
    if (scanf("%d", &N) && N > 0) {
        for (i = 0; i < N; ++i) scanf("%d", &a[i]);

        int max = INT_MIN;
        j = 0;
        for (j = 0; j < N; ++j) {
            memset(s, 0, sizeof(s));
            for (i = 0; i < N; ++i) {
                p[i] = a[(i+j)%N];
                p[i+1] = a[(i+j+1)%N];
            }

            dp();
            //print(1, N);
            //printf("%d\n", d[1][N]);
            max = max > d[1][N] ? max : d[1][N];
        }
        printf("%d\n", max);
    }
    return 0;
}