rt.可以被卡成指数级的暴力过了。

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, a[N], ans;
int dfs(int l, int r, int x){
  if(l > r)return 0;
  if(l == r)return 1;
  int mi = 1e9, cnt = 0;
  for(int i = l; i <= r; i++){
    if(a[i] == mi)cnt++;
    if(a[i] < mi){
      mi = a[i];
      cnt = 1;
    }
  }
  int last = l, sum1 = 0, sum2 = 0;
  for(int i = l; i <= r; i++){
    if(mi == a[i]){
      sum1 += dfs(last, i - 1, mi);
      sum2 += dfs(last, i - 1, x);
      last = i + 1;
    }
  }
  sum1 += dfs(last, r, mi);
  sum2 += dfs(last, r, x);
  return min(sum1 + mi - x, sum2 + cnt);
}
int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  cout << dfs(1, n, 0) << '\n';
  return 0;
}

HACK

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100