乘法谜题题解

题目分析

本题要求通过选择取卡片的顺序，使得总得分最小。每次取卡片时，得分等于该卡片与左右两边卡片的乘积，且不能取首尾卡片。最终只剩下两张卡片，求最小总得分。

状态定义

设 $dp[i][j]$ 表示在保留第 $i$ 张和第 $j+1$ 张卡片的情况下，取完中间所有卡片（$i+1$ 到 $j$）的最小得分。

状态转移方程

对于区间 $[i, j]$，枚举最后一个取的卡片 $k+1$（$i \leq k < j$），则得分由三部分组成：

1. 左区间 $[i, k]$ 的最小得分 $dp[i][k]$
2. 右区间 $[k+1, j]$ 的最小得分 $dp[k+1][j]$
3. 取卡片 $k+1$ 时的得分 $v[i] \times v[k+1] \times v[j+1]$（左右边界为 $i$ 和 $j+1$）

状态转移方程为：
$dp[i][j]=min(dp[i][k]+dp[k+1][j]+v[i]×v[k+1]×v[j+1])$

初始条件

当区间长度为 $1$ 时（$i = j$），中间没有卡片可取，得分 $dp[i][i] = 0$。

遍历顺序

按区间长度从小到大计算，先处理短区间，再处理长区间，确保计算长区间时子区间的解已求出。

代码解析

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 2147483647
const int maxn = 100 + 10;
int dp[maxn][maxn];  // dp[i][j] 表示保留i和j+1时的最小得分
int v[maxn];         // 卡片数值，索引从1开始
int n;

int main() {
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &v[i]);
            dp[i][i] = 0;  // 初始条件：区间长度为1时得分0
        }
        int t = n - 1; // 最后保留的两张卡片是v[1]和v[n]，中间处理1~t的区间
        // 按区间长度递增计算
        for (int len = 2; len <= t; len++) {  // len为区间[i,j]的长度（j-i+1）
            for (int i = 1; i <= t - len + 1; i++) {
                int j = i + len - 1;  // 终点位置
                dp[i][j] = INF;      // 初始化为无穷大
                // 枚举最后一个取的卡片k+1（i ≤ k < j）
                for (int k = i; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + v[i] * v[k+1] * v[j+1]);
                }
            }
        }
        printf("%d\n", dp[1][t]);  // 最终结果：处理区间[1, t]，对应左右边界v[1]和v[n]
    }
    return 0;
}

关键点说明

1. 区间定义：
   代码中 $dp[i][j]$ 处理的是中间卡片 $i+1$ 到 $j$，保留左右边界 $v[i]$ 和 $v[j+1]$，这样可以统一处理首尾不可取的条件。

2. 状态转移逻辑：
   通过枚举最后一个取的卡片，将问题分解为左右子区间的最优解，确保每次取卡片时左右边界存在（非首尾）。

3. 时间复杂度：
   三层循环，时间复杂度为 $O(n^3)$，适用于 $n \leq 100$ 的规模。

示例验证

以输入数据为例：

6  
10 1 50 50 20 5  

卡片数组为 $v = [0, 10, 1, 50, 50, 20, 5]$（索引从1开始），$t = 5$。
通过动态规划计算 $dp[1][5]$，最终得到最小得分为 3650，与样例输出一致。

总结

本题通过动态规划将问题分解为子区间的最优解，利用枚举最后一步操作的方法转移状态，有效避免了暴力枚举的指数级复杂度，是典型的区间动态规划应用。