【题目来源】
洛谷：P1063 [NOIP 2006 提高组] 能量项链 - 洛谷
【题目来源】
在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 \(N\) 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 \(m\)，尾标记为 \(r\)，后一颗能量珠的头标记为 \(r\)，尾标记为 \(n\)，则聚合后释放的能量为 \(m×r×n\)（Mars 单位），新产生的珠子的头标记为 \(m\)，尾标记为 \(n\)。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设 \(N\)\(=\)\(4\)，\(4\) 颗珠子的头标记与尾标记依次为 \((2,3)(3,5)(5,10)(10,2)\)。我们用记号 \(⊕\) 表示两颗珠子的聚合操作，\((j⊕k)\) 表示第 \(j,k\) 两颗珠子聚合后所释放的能量。则第 \(4\)，\(1\) 两颗珠子聚合后释放的能量为：
\((4⊕1)=10×2×3=60\)。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为：
\((((4⊕1)⊕2)⊕3)=10×2×3+10×3×5+10×5×10=710\)。
【输入】
第一行是一个正整数 \(N（4≤N≤100）\)，表示项链上珠子的个数。第二行是 \(N\) 个用空格隔开的正整数，所有的数均不超过 \(1000\)。第 \(i\) 个数为第 \(i\) 颗珠子的头标记（\(1≤i≤N\)），当 \(i\)\(<\)\(N\) 时，第 \(i\) 颗珠子的尾标记应该等于第 \(i+1\) 颗珠子的头标记。第 \(N\) 颗珠子的尾标记应该等于第 \(1\) 颗珠子的头标记。
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
【输出】
一个正整数 \(E（E≤2.1×10^9）\)，为一个最优聚合顺序所释放的总能量。
【输入样例】
4
2 3 5 10
【输出样例】
710
【算法标签】
《洛谷 P1063 能量项链》 #动态规划DP# #递归# #枚举# #区间DP# #NOIP提高组# #2006#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 205; // 定义最大珠子数量（环形展开后为2N）
int n; // 珠子数量
int a[N]; // 珠子能量数组（环形展开后）
int f[N][N]; // DP数组，f[i][j]表示合并i到j珠子的最大能量
int ans; // 存储最终结果int main()
{// 输入珠子数量cin >> n;// 输入每个珠子的头标记，并环形展开（复制一份到数组尾部）for (int i = 1; i <= n; i++){cin >> a[i];a[i + n] = a[i]; // 环形处理：将数组复制一份接在后面}// 动态规划求解for (int len = 3; len <= n + 1; len++) // len表示区间长度（至少3个珠子才能合并）{for (int i = 1; i + len - 1 <= 2 * n; i++) // 遍历所有起始点i{int j = i + len - 1; // 计算区间终点j// 遍历所有可能的分割点kfor (int k = i + 1; k < j; k++){// 状态转移方程：合并i-k和k-j的能量，加上本次合并产生的能量f[i][j] = max(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);}// 当区间长度等于n+1时（即完整环形区间），更新最终答案if (len == n + 1)ans = max(ans, f[i][j]);}}// 输出最大能量值cout << ans << endl;return 0;
}
【运行结果】
4
2 3 5 10
710