CWOI J C103C 红裤衩

给定一个长度为 $n$ 的序列 $a_i$。若 $a_i = \frac{a_{i-1}+a_{i+1}}{2}$，则可以删除 $a_i$，后面的数依次向前填充，求最少剩下多少数。

先差分。令 $d_i = a_i - a_{i-1}$，则 $a_i = \frac{a_{i-1}+a{i+1}}{2}$ 等同于 $d_i = d_{i+1}$，删除也就是把 $d_i$ 和 $d_j$ 合并，即翻倍。

$d_i$ 只能不断翻倍，故若 $\frac{d_i}{\mathrm{lowbit}(d_i)} \neq \frac{d_j}{\mathrm{lowbit}(d_j)}$，则 $d_i$ 和 $d_j$ 一定不能合并（$d_i=0$ 特殊讨论）。可以按照 $\frac{d_i}{\mathrm{lowbit}(d_i)}$ 把 $d$ 数组划分。

定义 $pre(i) = \frac{d_i}{\mathrm{lowbit}(d_i)}$，定义 $f(i)$ 表示前 $i$ 个最多合并个数，$g(i, j)$ 表示以 $i$ 为右端点，合并出 $pre(i) \times 2^j$ 的左端点，用类似倍增的方法转移 $g$，通过 $g$ 转移 $f$。

constexpr unsigned long long lowbit(unsigned long long x) { return x & -x; }
constexpr unsigned long long getexp(unsigned long long x) { return std::popcount(lowbit(x) - 1); }

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> a(n);
    for (auto &i : a) scanf("%d", &i);
    std::vector<long long> da(n);
    for (int i = 1; i < n; i++) da[i] = (long long)a[i] - a[i - 1];

    int ans = n;
    {
        int i = 1;
        while (i < n) {
            int j = i + 1;
            if (da[i] == 0) {
                while (j < n && da[j] == 0) j++;
                ans -= j - i - 1;
            } else {
                auto pre = da[i] / (signed)lowbit(std::abs(da[i]));
                while (j < n && da[j] != 0 && da[j] / (signed)lowbit(std::abs(da[j])) == pre) j++;
                std::vector<int> f(j - i);
                std::vector<std::vector<int>> g(j - i, std::vector<int>(32, -1));
                for (int p = 0; p < j - i; p++) {
                    int mink = getexp(std::abs(da[p + i]));
                    g[p][mink] = p;
                    if (p > 0) f[p] = f[p - 1];
                    for (int k = mink + 1; k < 32; k++) {
                        if (g[p][k - 1] - 1 >= 0 && g[g[p][k - 1] - 1][k - 1] >= 0) {
                            g[p][k] = g[g[p][k - 1] - 1][k - 1];
                            if (g[p][k] > 0) f[p] = std::max(f[p], f[g[p][k] - 1] + (p - g[p][k]));
                            else f[p] = std::max(f[p], p - g[p][k]);
                        }
                    }
                }
                ans -= f.back();
            }
            i = j;
        }
    }
    printf("%d\n", ans);
}

代码时注意处理负数、0 的情况。