短路

显然可以得出一个结论,一个数字大的点肯定要到一个数字比他小的点,这个我们可以用单调栈维护出来比一个点小的第一个点,然后 \(dp\) 即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 5;

int n, a[N], pos[N], dp[N], sum[N], pre[N];

int dfs(int x) {
  if (pre[x] == x) {
    return x;
  }
  return dfs(pre[x]);
}

signed main() {
  cin >> n;
  n++;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  stack<int> stk;
  for (int i = 1; i <= n; i++) {
    while (!stk.empty() && a[stk.top()] >= a[i]) {
      stk.pop();
    }
    if (!stk.empty()) {
      pos[i] = stk.top();
    }
    else pos[i] = 0;
    stk.push(i);
  }
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = dp[pos[i]] + (i - pos[i] + 1) * a[i] + sum[i - 1] - sum[pos[i]];
    pre[i] = pos[i];
    if (pos[i] == 0) {
      pre[i] = i;
    }
    if ((i * 2 - 1) * a[i] < dp[i]) {
      dp[i] = (i * 2 - 1) * a[i];
      pre[i] = i;
    }
  }
  cout << dp[n] * 2 - a[dfs(n)];
  return 0;
}

天路

我们一定要注意到他所说的十分重要的那句话!!!!!!我们可以大概画出答案随值的变化函数

那么虽然 \(100\) 和 \(105\) 对应的答案不同,但是我们可以都直接输出 \(100\),那么我们大概可以想到我们可以枚举 \(1.05\) 的次方,每次看最大能包含多长的区间然后输出即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 5;

int n, a[N];

deque<int> qmax, qmin;

void Insert(int i) {
  while (!qmax.empty() && a[qmax.back()] < a[i]) {
    qmax.pop_back();
  }
  qmax.push_back(i);
  while (!qmin.empty() && a[qmin.back()] > a[i]) {
    qmin.pop_back();
  }
  qmin.push_back(i);
}

void Erase(int i) {
  if (!qmax.empty() && qmax.front() == i) {
    qmax.pop_front();
  }
  if (!qmin.empty() && qmin.front() == i) {
    qmin.pop_front();
  }
}

signed main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int l = 0, last = 2; l <= 1000000; l = (l + 1) * 1.05) {
    int r = 0;
    qmax.clear(), qmin.clear();
    for (int i = 1, j = 1; i <= n; i++) {
      while (j <= n && (j == i || max(a[j], a[qmax.front()]) - min(a[j], a[qmin.front()]) <= (l + 1) * 1.05 - 1)) {
        Insert(j);
        j++;
      }
      r = max(r, j - i);
      Erase(i);
    }
    for (int i = last; i <= r; i++) {
      cout << l << "\n";
    }
    if (last <= r) {
      last = r + 1;
    }
  }
  return 0;
}