P1063 能量项链 题解

题意简述

给定一个链，链上有$N$个珠子，不同珠子合并会产生不同的能量，问：按照什么样的顺序合并这$N$个珠子能产生最大的能量？

题目分析

1. 因为题目中所给的是环，我们需要将其转化为链，可以将环断开，拼成一个长度为$2N$的长链，每个新链上第$i + N$颗珠子都对应着原链上第$i$颗珠子。

2. 接下来就需要考虑利用区间$dp$算法，来进行状态定义：

定义$dp[i][j]$表示将区间$[i, j]$的珠子合并为一颗珠子所产生的能量（当然是最大的）。

3. 状态转移方程： 考虑用一个分割点$k(i \le k < j)$将区间$[i, j]$分割为$[i, k]$和$[k + 1, j]$两个区间，将这两个区间合并成的珠子进行合并，那么状态便可以这样转移。

• 区间$[i,k]$合并成一个（头$h_i$, 尾$h_{k + 1}$）的珠子；

• 区间$[k+1, j]$合并成一个（头$h_{k + 1}$, 尾$h_{j + 1}$）的珠子；

• 那么新合并地珠子便可以表示成三个部分

• 1. $f[i][k]$，

  2. $f[k + 1][j]$

  3. $h_i \times\ h_{k + 1} \times\ h_{j + 1}$

  所以总能量为$f[i][k] + f[k + 1][j] + h_i \times\ h_{k + 1} \times\ h_{j + 1}$

  我们可以通过枚举分割点$k(i \le\ 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(N ^3)$（适用于$N \le\ 10 ^ 2$ 的数据）

空间复杂度： $O(N^2)$

结语

考场上能识别出这道题考查的是区间$dp$算法才是关键，根据状态定义来推出状态转移方程！