题目描述

合并相邻石子到一堆的最小代价，其中

$$相邻的[l, r]合并的代价=weight[l] + weight[r]$$

样例

输入

4
1 3 5 2

结果

22

(记忆化搜索) $O(n^3)$

我们要解决的问题=合并相邻石子的最小代价

因此比较容易想到的第一个思路是枚举分割点

比如我们要求[l, r]区间的最小合并代价，这部分区间最终合并成一堆的代价是固定的，等于一个区间合。因此我们需要做的就是枚举分割点，求分割点左右侧的最小合并代价，因此可以得到

min[l, r]的代价 = min[l, mid] + min[mid + 1, r] + acc[l, r]

时间复杂度

N是区间的长度，由于使用了记忆化，每个状态只会算一次，因此这个

$$ 复杂度 = 状态个数 \times 单个状态计算复杂度 $$

状态个数为$O(n^2)$, 每个状态里的枚举复杂度是$O(n)$

C++ 代码

#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>

// Created by Simonhancrew on 2024/11/12

using namespace std;

using LL = long long;
using PII = pair<int, int>;
#define fast_cin()                  \
  ios_base::sync_with_stdio(false); \
  cin.tie(nullptr);                 \
  cout.tie(nullptr)

const int INF = 0x3f3f3f3f, N = 310;

int n;
int a[N];
int f[N][N];

int dfs(int l, int r) {
  if (l >= r) {
    return 0;
  }
  auto& res = f[l][r];
  if (res != -1) {
    return res;
  }
  res = INT_MAX;
  auto sum = a[r] - a[l - 1];
  for (int mid = l; mid < r; mid++) {
    res = min(res, dfs(l, mid) + dfs(mid + 1, r) + sum);
  }
  return res;
}

int main() {
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  fast_cin();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  memset(f, -1, sizeof f);
  cout << dfs(1, n) << '\n';
  return 0;
}