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 的情況。