P4896 选取书籍（提高）

解题思路

第一步，读懂题目。 书架上有一列 M 本书，每本有价格。读者要取走中间的书（第一本和最后一本不许取），每次取走一本要付"这本书的价格 × 它左边书的价格 × 它右边书的价格"这么多钱。取完所有能取的书后，问总共最少付多少钱。

第二步，区间 DP 的思路。 设 dp[i][j] 表示"把第 i 本到第 j 本之间的书全部取走的最少花费"（i 和 j 这两本最后留着）。取书的过程可以倒过来想：最后取走的那本一定是中间某一本 k，它取走时左右两边正好是 i 和 j，这一笔费用是 a[i]×a[k]×a[j]；而在这之前，i..k 之间和 k..j 之间的书已经被取光了。

第三步，写状态转移。 dp[i][j] = min（dp[i][k] + dp[k][j] + a[i]×a[k]×a[j]），其中 k 从 i+1 到 j-1。就像剥洋葱，一层一层从短区间算到长区间：先算区间长度为 2 的（中间没有书，费用是 0），再算长度为 3、4……直到整个 [1,M]。

具体例子： 样例 4 本书 5 3 2 9。如果先取第 2 本（价格 3），费用 5×3×2=30，剩下 5 2 9；再取中间那本 2，费用 5×2×9=90，总共 120。如果先取 2 再取 3，总共 135。所以最少是 120。

边界情况： 第一本和最后一本不能取，所以最终答案就是 dp[1][M]。中间没有书的区间 dp[i][i+1]=0。价格乘积可能超过 int 范围，要用 long long。

参考代码

// 选取书籍：取走中间书支付 价格*左右价格,求最小总支付,区间DP
#include <iostream>
using namespace std;

int m, a[210];
long long dp[210][210]; // dp[i][j]为取走i..j中间所有书的最小费用

int main() {
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int len = 3; len <= m; len++) {       // 区间长度至少3
        for (int i = 1; i + len - 1 <= m; i++) {
            int j = i + len - 1;
            long long mn = 1LL << 62;
            for (int k = i + 1; k < j; k++) {  // 最后取走的书
                long long x = dp[i][k] + dp[k][j] + (long long)a[i] * a[k] * a[j];
                if (x < mn) mn = x;
            }
            dp[i][j] = mn;
        }
    }
    cout << dp[1][m] << endl;
    return 0;
}

复杂度分析

区间长度有 M 种，每个区间要枚举中间分点 k，所以时间复杂度是 O(M³)。M 最大约 200，约 10⁷ 次计算，可以接受。空间上需要一张 M×M 的表，是 O(M²)。