P4910 抽卡片（提高）

解题思路

第一步，理解题意。 N张卡片摆成一行，每张卡片上写着一个正整数。游戏过程中，玩家每次从这一行里取出一张卡片，但不能取第一张和最后一张。取出一张卡片k的得分，等于k左边的卡片、k本身、k右边卡片三个数字相乘。目标是把中间所有卡片都取完，并且让总得分最少。

第二步，发现区间的结构。 假设现在区间(i,j)里只留下了最左边的卡片i和最右边的卡片j，它们之间的卡片都已经被取走了。观察发现，最后被取出的那张卡片k一定在i和j之间，它被取走时i和j都还留在场上，所以这次得分就是a[i]×a[k]×a[j]。在取k之前，k左边的区间(i,k)和右边的区间(k,j)里的卡片必须都已经取完。

第三步，设计动态规划。 定义dp[i][j]表示把区间(i,j)内的所有卡片取完需要的最小得分（i和j这两张不取）。相邻两张卡片之间没有可取的卡片，所以dp[i][i+1]=0。转移方程：dp[i][j]取min( dp[i][k] + dp[k][j] + a[i]*a[k]*a[j] )，其中k遍历i+1到j-1。

第四步，按区间长度从小到大递推。 因为计算长区间要用到短区间，所以外层循环从小到大枚举区间长度len，内层枚举左端点i，右端点j=i+len。例如样例10 1 50 50 20 5，最终dp[0][5]=3650，与样例输出一致。

第五步，注意细节。 数字范围1到100，三张相乘最大100万，总得分不会超过int的范围，但稳妥起见用long long存储。当N=3时，区间(0,2)里只有k=1这一张卡可取，答案就是a[0]*a[1]*a[2]。因为第一张和最后一张永远不能取，最终正好剩下这两张，答案就是dp[0][N-1]。

参考代码

// 抽卡片：区间DP，dp[i][j]表示区间(i,j)内卡片被取完的最小得分
#include <iostream>
using namespace std;
long long a[105];
long long dp[105][105];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    // len为区间跨度，相邻两张卡片之间无卡片可取，dp[i][i+1]为0
    for (int len = 2; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            long long best = 1e18;
            // 枚举最后一张取k，此时k的左右两边正是i和j
            for (int k = i + 1; k < j; k++) {
                long long cur = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
                if (cur < best) best = cur;
            }
            dp[i][j] = best;
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}

复杂度分析

一共有O(N²)个区间，每个区间要枚举O(N)个k，所以时间复杂度是O(N³)。N最大是100，100³等于100万次运算，完全可以承受。dp数组的大小是N×N，空间复杂度O(N²)。每张卡片的数字不超过100，三个数相乘最大100万，总得分用long long存放安全无溢出。