主要思路

想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。

考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。

如果是这样的话，那么我们可以试着先做一个区间 DP。设置 \(dp[l][r]\) 使得这一段区间全部清空、端点进行保留，那么构造出 \(c_l = p_l, c_i = \max(p_i – c_{i – 1}, 0)\)，得到：

\[ \begin{aligned} f[l][r] &= \sum_{i = l}^{r – 2} c_i + c_{r – 1} + c_r \\ &= f[l][r – 2] + \max(p_r – c_{r – 1}, 0) + c_{r – 1} \\ &= f[l][r – 2] + \max(p_r, c_{r – 1}) \\ &\leq f[l][r – 2] + p_r \\ &= f[l][r – 2] + f[r][r] \end{aligned} \]

那么可以用这个直接做线性的 DP，讨论一下不同的长度，然后再反过去即可。

代码

// CF933E.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200;

typedef long long ll;

int n, ai[MAX_N], pi[MAX_N];
ll f[MAX_N];
bool opt[MAX_N];
vector<int> ans;

int process(int pos)
{
    int val = min(ai[pos], ai[pos + 1]);
    if (val)
        ans.push_back(pos);
    ai[pos] -= val, ai[pos + 1] -= val;
    return val;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ai[i]);
        ll single = f[max(0, i - 2)] + ai[i], binary = f[max(0, i - 3)] + max(ai[i], ai[i - 1]);
        f[i] = min(single, binary), opt[i] = f[i] != single;
    }
    int cnt = 0;
    for (int i = min(f[n - 1], f[n]) == f[n - 1] ? n - 1 : n; i >= 1; i -= (opt[i] == true) + 2)
        pi[++cnt] = i;
    reverse(pi + 1, pi + 1 + cnt);
    for (int i = 1; i <= cnt; i++)
    {
        int pre = pi[i - 1], curt = pi[i];
        ll acc = 0;
        if (opt[curt])
            acc += process(curt - 1);
        acc += process(pre + 1), acc += process(curt);
    }
    printf("%lld\n", 1LL * ans.size());
    for (auto &x : ans)
        printf("%d\n", x);
    puts("");
    return 0;
}