P1063 能量项链 题解
题意简述
给定一个链，链上有N个珠子，不同珠子合并会产生不同的能量，问：按照什么样的顺序合并这N个珠子能产生最大的能量？
题目分析
-
因为题目中所给的是环，我们需要将其转化为链，可以将环断开，拼成一个长度为2N的长链，每个新链上第i+N颗珠子都对应着原链上第i颗珠子。
-
接下来就需要考虑利用区间dp算法，来进行状态定义：
定义dp[i][j]表示将区间[i,j]的珠子合并为一颗珠子所产生的能量（当然是最大的）。
- 状态转移方程： 考虑用一个分割点k(i≤k<j)将区间[i,j]分割为[i,k]和[k+1,j]两个区间，将这两个区间合并成的珠子进行合并，那么状态便可以这样转移。
-
区间[i,k]合并成一个（头hi, 尾hk+1）的珠子；
-
区间[k+1,j]合并成一个（头hk+1, 尾hj+1）的珠子；
-
那么新合并地珠子便可以表示成三个部分
-
-
f[i][k]，
-
f[k+1][j]
-
hi× hk+1× hj+1
所以总能量为$f[i][k] + f[k + 1][j] + h_i \times\ h_{k + 1} \times\ h_{j + 1}$
我们可以通过枚举分割点k(i≤ k<j)来求合并产生能量的最大值
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105;
int n, h[N * 2], f[N * 2][N * 2];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1;i <= n; i++) {
cin >> h[i];
h[i + n] = h[i];
}
for(int l = 2;l <= n; l++) {
for(int i = 1;i <= 2 * n - l; i++) {
int j = i + l - 1;
for(int k = i;k < j; k++) {
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + h[i] * h[k + 1] * h[j + 1]);
}
}
}
int ans = 0;
for(int i = 1;i <= n; i++) ans = max(ans, f[i][i + n - 1]);
cout << ans;
return 0;
}
时间复杂度： O(N3)（适用于N≤ 102 的数据）
空间复杂度： O(N2)
结语
考场上能识别出这道题考查的是区间dp算法才是关键，根据状态定义来推出状态转移方程！
zhangze 2026-4-4 21:55:05