容易想到枚举最大值，令 \(f_{i, j}\) 表示前 \(i\) 个数变为不降序列且第 \(i\) 个数为 \(j\) 的最小操作次数。
先考虑暴力转移：\(f_{i,j} = f_{i - 1, k} + \text{chg}(a_i, j)\)，其中 \(\text{chg}(i, j)\) 表示 \(i\) 到 \(j\) 的最少操作次数。这样是 \(\mathcal{O}(nV^2)\) 的，但能过，应该是因为有一个 \(\frac{1}{2}\) 的常数。
考虑优化。
发现 \(\text{chg}(a_i, j)\) 是不变的，处理出 \(lst_j\) 表示第 \(i - 1\) 个小于等于 \(j\) 时，操作的最少次数，这样就可以 \(\mathcal{O}(1)\) 转移了。
不升序列同理。
时间复杂度：\(\mathcal{O}(nV)\)。
代码：
const int N = 5e6 + 10;
int n;
int a[N], lst[10];
int f[N][10], g[N][10];
int chg(int x, int y) {
if (x < y) swap(x, y);
return min(x - y, y + 10 - x);
}
int main() {
ios
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
memset(f, 0x3f, sizeof(f)), memset(g, 0x3f, sizeof(g));
for (int i = 0; i <= 9; i++)
f[1][i] = chg(i, a[1]);
for (int i = 0; i <= 9; i++)
g[n][i] = chg(i, a[n]);
for (int i = 2; i <= n; i++) {
lst[0] = f[i - 1][0];
for (int j = 1; j <= 9; j++) lst[j] = min(lst[j - 1], f[i - 1][j]);
for (int j = 0; j <= 9; j++)
f[i][j] = lst[j] + chg(a[i], j);
}
for (int i = n - 1; i >= 1; i--) {
lst[0] = g[i + 1][0];
for (int j = 1; j <= 9; j++) lst[j] = min(lst[j - 1], g[i + 1][j]);
for (int j = 0; j <= 9; j++)
g[i][j] = lst[j] + chg(a[i], j);
}
int ans = inf;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 9; j++)
ans = min(ans, f[i][j] + g[i][j] - chg(j, a[i]));
cout << ans << "\n";
return 0;
}