• 与本题有很多相似的题

P2101 命运石之门的选择

CF1400E Clear the Multiset

P1969 [NOIP2013 提高组] 积木大赛

P5019 [NOIP2018 提高组] 铺设道路

P3078 [USACO13MAR]Poker Hands S

[ABC116C] Grand Garden

• 说明本题的模型还是很重要的, 需要完全弄清楚, 下面提供本题的两份AC代码.

• 第一份代码, 难点在时间复杂度的分析.

• 第二份代码, 通过多记录一个h, 就可以做了.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e3 + 5;
int n, a[N];

// 将[l, r]区间刷完的最小操作次数.
// 考虑找到[l, r]区间的最小值, 那么[l, r]区间的每个数都可以减去这个最小值, 然后递归分治处理.
// 各个区间不会重叠, 所以不需要记忆化.

// 时间复杂度: 如果按照一般的区间dp, 会以为是O(N ^ 3)的, 其实不是.
// 因为我们每次从[l, r]区间里选一个点出来, 总共选n个不同的点花费O(n), 每次选一个点时遍历[l, r]花费O(n).
// 所以总的时间复杂度为O(n ^ 2)
int dfs(int l, int r) {
  if (l > r) return 0;
  if (l == r) return std::min(a[l], 1);
  // 找到[l, r]区间的最小值
  int minV = a[l], minV_Pos = l;
  for (int i = l; i <= r; ++i) {
    if (a[i] < minV) {
      minV = a[i];
      minV_Pos = i;
    }
  }
  // [l, r]区间都减去这个最小值
  for (int i = l; i <= r; ++i) a[i] -= minV;
  // 递归分治处理
  return std::min(r - l + 1, dfs(l, minV_Pos - 1) + dfs(minV_Pos + 1, r) + minV);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  cout << dfs(1, n);
  return 0;
}

第二份代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 5e3 + 5;
int n, a[N];
std::unordered_map<string, int> dp;

// 定义dp[i][h]表示将[i, n]的区间刷完时的最小操作数, h表示从i的左侧而来的有效横刷高度.
// 转移: 考虑对第i个位置竖着涂还是横着涂.
// 时间复杂度: i有n种情况, h也只有n种情况, 总的时间复杂度为O(N ^ 2). 忽略unordered_map的开销.
// 一个值得注意的点是: h只会是数组a[1...n]的某一个, 所以h最多有n种情况.
int dfs(int i, int h) {
  if (i == n + 1) return 0;
  string str = std::to_string(i) + "#" + std::to_string(h);
  if (dp.count(str)) return dp[str];

  int ret = n;
  // 竖着涂
  ret = std::min(ret, dfs(i + 1, std::min(h, a[i])) + 1);
  // 横着涂
  ret = std::min(ret, dfs(i + 1, a[i]) + max(a[i] - h, 0));
  return dp[str] = ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  cout << dfs(1, 0);
  return 0;
}