PP4906 外星微生物（基础）

解题思路

第一步，识别问题。 一排生物只能相邻合并，合并成本是两者体重之和，最后要合成一个。这是经典的"石子合并"区间 DP 问题。

第二步，设计状态。 用 dp[i][j] 表示"把第 i 到第 j 个生物合并成一个生物的最小消耗"。单个生物不需要合并，所以 dp[i][i]=0。

第三步，枚举分割点。 要合并 i..j，可以先把它分成左段 i..k 和右段 k+1..j，先把两段分别合并好（花费 dp[i][k]+dp[k+1][j]），最后再把这两大坨合并（花费 s[j]-s[i-1]，即这一段的总重量）。取所有分割点 k 的最小值。

第四步，区间从小到大填表。 用前缀和数组 s 快速求一段的重量。外层循环区间长度 len，内层枚举起点 i，再枚举分割点 k。

边界情况。 样例 2、3、5 合并：先把 2 和 3 合并成 5（花 5），再和 5 合并成 10（花 10），总消耗 15。用 long long 存答案，避免大数溢出。

参考代码

// P4906 外星微生物 区间DP：相邻两个合并，求最小总消耗
#include <iostream>
using namespace std;
long long w[105], s[105]; // w 体重, s 前缀和
long long dp[105][105]; // dp[i][j] 把 i..j 合并成一个的最小消耗
int main() {
    int n, i, j, k, len;
    cin >> n;
    for (i = 1; i <= n; i++) { cin >> w[i]; s[i] = s[i - 1] + w[i]; }
    // len 是区间长度，从短到长填表
    for (len = 2; len <= n; len++) {
        for (i = 1; i + len - 1 <= n; i++) {
            j = i + len - 1;
            dp[i][j] = 1LL << 60; // 先设成很大的数
            for (k = i; k < j; k++) {
                // 先合并左段和右段，最后再合并这两段
                long long cost = dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1];
                if (cost < dp[i][j]) dp[i][j] = cost;
            }
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(n^3)（区间数 O(n^2)，每个区间枚举分割点 O(n)），n≤100 完全可行。空间复杂度 O(n^2)。