[NOI1995] 石子合并 题解

对于这个问题，可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示将区间[i, j]的石子合并成一堆所需要的最小代价。

首先，我们可以考虑合并长度为2的石子堆，即dp[i][j] = dp[i][i+1] + dp[i+2][j] + sum(i, j)，其中sum(i, j)表示区间[i, j]的石子堆的总和。然后，我们可以逐步增加合并的长度，直到合并整个区间。

具体的动态规划转移方程如下：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i, j))，其中i ≤ k < j

最后，所求的答案即为dp[n]，其中n为石子堆的数量。

以下是C++的代码实现：

const int MAXN = 105;
int dp[MAXN][MAXN];
int sum[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i-1]; // 计算前缀和
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
            }
        }
    }

    cout << dp[1][n] << endl;

    return 0;
}

希望这个解法能够帮助你解决问题！