Ý tưởng

Giả sử ta chọn ~A_x~ là đỉnh núi:

• Gọi ~lt[i]~ là chi phí biến đổi dãy ~A_1, A_2, \dots, A_i~ thành dãy tăng đơn điệu, và ~p\_lt[i]~ là giá trị của ~A_i~ sau khi biến đổi.

Ví dụ: Với ~n = 4~ và ~A = [1, 1, 1, 1]~, ta có ~lt = [0, 1, 3, 6]~ và ~p\_lt = [1, 2, 3, 4]~.

• Gọi ~rt[i]~ là chi phí biến đổi dãy ~A_i, A_{i + 1}, \dots, A_n~ thành dãy giảm đơn điệu, và ~p\_rt[i]~ là giá trị của ~A_i~ sau khi biến đổi.

Ví dụ: Với ~n = 4~ và ~A = [1, 1, 1, 1]~, ta có ~rt = [6, 3, 1, 0]~ và ~p\_rt = [4, 3, 2, 1]~.

~\Rightarrow~ Chi phí khi chọn ~A_x~ là đỉnh núi: ~lt[x] + rt[x] - min(p\_lt[x], p\_rt[x]) + A_x~.

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

const int maxN = 1e5 + 7;

int n, arr[maxN];
long long lt[maxN], rt[maxN], p_lt[maxN], p_rt[maxN], ans = 1e18 + 7;

void input()
{
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];
}

void solve()
{
    p_lt[0] = arr[0];
    lt[0] = 0;
    for(int i = 1; i < n; ++i)
    {
        lt[i] = lt[i - 1];
        if(p_lt[i - 1] >= arr[i])
        {
            lt[i] += p_lt[i - 1] - arr[i] + 1;
            p_lt[i] = p_lt[i - 1] + 1;
        }
        else p_lt[i] = arr[i];
    }
    p_rt[n - 1] = arr[n - 1];
    rt[n - 1] = 0;
    for(int i = n - 2; i >= 0; --i)
    {
        rt[i] = rt[i + 1];
        if(p_rt[i + 1] >= arr[i])
        {
            rt[i] += p_rt[i + 1] - arr[i] + 1;
            p_rt[i] = p_rt[i + 1] + 1;
        }
        else p_rt[i] = arr[i];
    }
    for(int i = 1; i < n - 1; ++i)
    {
        ans = min(ans, rt[i] + lt[i] - min(p_lt[i], p_rt[i]) + arr[i]);
    }
    cout << ans;
}

int main()
{
    freopen("dapnui.inp", "r", stdin);
    freopen("dapnui.out", "w", stdout);
    input();
    solve();
    return 0;
}