[P3580] [POI2014] ZAL - Freight

不难发现最优方案一定是把序列划成若干段，从左到右依次每段走过去再走回来。

首先遍历 (i) 从 (2) 到 (n)，令 (t_i = max(t_i, t_{i - 1}))，为的是使最早出发时间满足间隔至少一秒。

不难列出 dp 方程 (dp_i = min_{1 le j < i} {max{dp_j + i - j - 1, t_i} + 2s + i - j - 1})。

考虑如何进行 dp 转移，如果没有取 max 操作即为维护 (dp_j - 2j) 的前缀最值。

对于 (j_1 < j_2)，若 (dp_{j_1} - 2j_1 ge dp_{j_2} - 2j_2)，则从 (j_2) 转移一定不劣于 (j_1)。

证明：

当 (max{dp_j + i - j - 1, t_i} = t_i) 时，称 (j) 取 max 成功。

若 (j_1,j_2) 均取 max 成功，(-j_1 > -j_2)，所以 (j_2) 更优。

若 (j_1,j_2) 均未取 max 成功，(dp_{j_1} - 2j_1 ge dp_{j_2} - 2j_2)，所以 (j_2) 更优。

若 (j_1) 成功而 (j_2) 未成功，(j_1) 取 max 前已经劣于 (j_2)，取 max 只会更劣，所以 (j_2) 更优。

若 (j_1) 未成功而 (j_2) 成功，(max{dp_{j_1} + i - {j_1} - 1, t_i} ge t_i)，(-j_1 > -j_2)，所以 (j_2) 更优。

证毕。

所以最优转移一定是考虑前 (i - 1) 个数时 (dp_j - 2j) 的后缀最小值。

用单调栈表示，这些位置 (j) 递增，(dp_j - 2j) 递增，所以 (dp_j - j) 也递增。

注意到取 max 成功的条件为 (dp_j - j le t_i - i + 1)，对应着单调栈的一段前缀，且分界点随 (i) 的增大单调后移。

若从取 max 成功的 (j) 转移，(j) 越大越优。

若从取 max 未成功的 (j) 转移，(dp_j - 2j) 越小越优，单调栈上即 (j) 越小越优。

dp 转移的过程中同时维护单调栈和分界点，从取 max 成功的最大 (j) 值和未成功的最小 (j) 值转移。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template <typename T>
inline void chkmax(T &x, const T &y) {
    if (x < y) x = y;
}
template <typename T>
inline void chkmin(T &x, const T &y) {
    if (y < x) x = y;
}
const int MAXN = 1e6 + 10;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
int n, s, t[MAXN], stk[MAXN], tp;
ll dp[MAXN];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) cin >> t[i];
    for (int i = 2; i <= n; ++i) chkmax(t[i], t[i - 1] + 1);
    stk[tp = 1] = 0;
    for (int i = 1, pos = 1; i <= n; ++i) {
        while (pos <= tp && dp[stk[pos]] - stk[pos] < t[i] - i + 1) ++pos;
        dp[i] = INFLL;
        if (pos <= tp)
            chkmin(dp[i], dp[stk[pos]] - stk[pos] * 2 + i * 2 + s * 2 - 2);
        if (pos > 1) chkmin(dp[i], (ll)t[i] + s * 2 + i - stk[pos - 1] - 1);
        while (tp && dp[i] - i * 2 <= dp[stk[tp]] - stk[tp] * 2) --tp;
        stk[++tp] = i, chkmin(pos, tp);
    }
    cout << dp[n] << "n";
    return 0;
}