我的思路是差分约束，在相邻两个人之间连边。

但是这道题标签好像是贪心，想不到贪心策略。

错误样例输入：

14
9 3 8 1 4 6 8 8 4 0 2 8 8 8

样例输出

28

实际输出

45

#include <bits/stdc++.h>
using pii = std::pair<int, int>;
const int N = 110;

bool vis[N];
std::queue<int> q;
std::vector<pii> g[N];
int ans, n, s[N], dis[N];

void add(int u, int v, int w) {
  g[u].push_back({v, w});
}

int main() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> s[i];

  for (int i = 1; i <= n; ++i) {
    if (i != n) {
      if (s[i] > s[i + 1]) add(i, i + 1, -1);
      else if (s[i] < s[i + 1]) add(i + 1, i, -1);
    }
  }

  memset(dis, 0x3f, sizeof(dis));
  dis[0] = 0;
  for (int i = 1; i <= n; ++i) add(0, i, 0);

  q.push(0);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = false;

    for (auto to : g[u]) {
      if (dis[to.first] > dis[u] + to.second) {
        dis[to.first] = dis[u] + to.second;
        if (!vis[to.first]) q.push(to.first), vis[to.first] = true;
      }
    }
  }


  int minn = *std::min_element(dis + 1, dis + n + 1);
  for (int i = 1; i <= n; ++i)
    ans += dis[i] - minn + 1;
  std::cout << ans << std::endl;

  return 0;
}