动态规划经典问题 石子合并

我们学校的oj的

#include <stdio.h>
#include <memory.h>
int sum[105][105] = {0};//合并后的状态分
int dp[105][105] = {0};//见下面注释
int p[105] = {0};
int n;

int dpMax(int start, int length) {
    int k, temp = 0;
    if (dp[start][length] != -1) {
        return dp[start][length]; //已经求过
    }
    dp[start][length] = 0;
    //枚举划分的情况
    for (k = 1; k <= length - 1; k++) {
        temp = dpMax(start, k) + dpMax((start + k - 1) % n + 1, length - k)
                + sum[start][length];
        if (temp > dp[start][length]) {
            dp[start][length] = temp;
        }
    }
    return dp[start][length];
}

int dpMin(int start, int length) {

    int k, temp = 0;
    if (dp[start][length] != -1) {
        return dp[start][length]; //已经求过
    }
    dp[start][length] = 32767;
    if (length == 1) {
        dp[start][length] = 0;
    }
    //枚举划分的情况
    for (k = 1; k <= length - 1; k++) {
        temp = dpMin(start, k) + dpMin((start + k - 1) % n + 1, length - k)
                + sum[start][length];
        if (temp < dp[start][length]) {
            dp[start][length] = temp;
        }
    }
    return dp[start][length];
}

/*
 * 动态规划经典问题 石子合并
 * 感谢黄大牛！！！
 * 在一个圆形操场的四周摆放着n 堆石子。
 * 现要将石子有次序地合并成一堆。
 * 规定每次只能选相邻的2 堆石子合并成新的一堆，
 * 并将新的一堆石子数记为该次合并的得分。
 * 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
 * input
 * 4
 * 4 4 5 9
 * output
 * 43
 * 54
 *
 * 设dp[i][k]表示以i为起点，长度为k的直线上各堆石子的最优合并状态
 * sum[i][k]表示以i为起点，长度为k的直线上各堆石子的总分
 * 枚举起点，变环为直线
 *
 * 对于每一条长度为k的直线有k-1种划分方法，
 *                  枚举后，就求出最优值
 * 如：4 4 5 9,看成已经合并后的一个大堆，共有3种划分，即
 * 4 459;44 59;445 9;看成是这三种情况下每两个堆的合并
 * dp[1][4]=dp[1][1]+dp[2][3]+sum[1][4]
 *         =dp[1][2]+dp[3][2]+sum[1][4]
 *         =dp[1][3]+dp[4][1]+sum[1][4]
 * 子问题再类似分解
 * dp[2][3]=dp[2][1]+dp[3][2]+sum[2][3]
 *         =dp[2][2]+dp[][]+sum[2][3]
 * dp[2][2]=dp[2][1]+dp[3][1]+sum[2][2]
 * dp[1][2]=dp[1][1]+dp[2][1]+sum[1][2]
 * dp[3][2]=dp[3][1]+dp[4][1]+sum[3][2]
 * dp[1][3]=dp[1][1]+dp[2][2]+sum[1][3]
 *         =dp[1][2]+dp[3][1]+sum[1][3]
 * 而dp[1][1]=4;dp[2][1]=4;dp[3][1]=5;dp[4][1]=9;
 * 从上递归或从下递推都能求得最优值
 * 也就是要把dp[][]和sum[][]这两张表填写完毕
 * 按照假设，这两张表要按列来填
 */
int main() {
    int i, j, max = 0, min = 32767, temp = 0;
    scanf("%d", &n);
    //输入
    for (i = 1; i <= n; i++) {
        scanf("%d", & p[i]);
    }
    memset(sum, 0, sizeof (sum));
    //填求和的表，按列填
    //第一列
    for (i = 1; i <= n; i++) {
        sum[i][1] = p[i];
    }
    //余下的
    for (j = 2; j <= n; j++) {
        for (i = 1; i <= n; i++) {
            sum[i][j] = sum[i % n + 1][j - 1] + sum[i][1]; //
        }
    }
    //
    memset(dp, -1, sizeof (dp));
    //枚举起点，变环为线
    for (i = 1; i <= n; i++) {
        temp = dpMin(i, n);
        if (temp < min) {
            min = temp;
        }
    }
    memset(dp, -1, sizeof (dp));
    //枚举起点，变环为线
    for (i = 1; i <= n; i++) {
        temp = dpMax(i, n);
        if (temp > max) {
            max = temp;
        }
    }
    printf("%d\n", min);
//    for(i=1;i<=n;i++){
//        for(int j=1;j<=n;j++){
//            printf("%d ",sum[i][j]);
//        }
//        printf("\n");
//    }
    printf("%d\n", max);

    return 1;
}