题解：AT_arc219_f [ARC219F] Range Division

· · 题解

设一个 a_i 的二进制表示下长度为 l_i，它总共被操作了 c_i 次，其中 c_i \ge l_i。则我们需要的最小操作次数为：（最低位以 1 开始编号）

\sum_{i = 1} ^ n c_i - \sum_{i = 1} ^ {n - 1} \text{lcs}(a_i[1 \ldots c_i], a_{i + 1}[1 \ldots c_{i + 1}]).

后面这一项表示的是有一些单点被合并成一个区间，可以省下的操作次数。

这个式子妙在：我们只需要关注 (i, i + 1) 的贡献。为什么这样不会让答案偏小呢？如果说 \text{lcs}(a_i[1 \ldots c_i], a_{i + 1}[1 \ldots c_{i + 1}]) 和 \text{lcs}(a_{i + 1}[1 \ldots c_{i + 1}], a_{i + 2}[1 \ldots c_{i + 2}]) 有交集，那么这次操作应当是节省了两个单点而不是一个单点，这个式子可以间接地把多出来的一个单点给减去了，因此正确。

接下来就可以设计 f_{i, j} 表示当前处理到第 i 个数，第 i 个数被操作 j 次的最小操作次数。在枚举 i 的时候处理 i - 1 和 i 的 \text{lcs} 数组 s_{a, b}，于是容易得到转移：

f_{i, j} = \min_{k}(f_{i - 1, k} + j - s_{k, j})

总时间复杂度 O(n^3 \log^2 V)。

/*
 * author: LostKeyToReach
 * created time: 2026-05-10 21:46:32
 */
#include <bits/stdc++.h>
#define int long long
#define vi std::vector<int>
#define eb emplace_back
using ll = long long;
using pii = std::pair<int, int>;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define chkmax(x, y) x = std::max(x, y)
#define chkmin(x, y) x = std::min(x, y)
int fio = (std::cin.tie(0)->sync_with_stdio(0), 0);
constexpr int N = 32, INF = 1e9;
int n, len, a[N], f[N][N * N * 2], l[N], dg[N][N * N * 2], lcs[N * N * 2][N * N * 2];
int32_t main() {
    int t; std::cin >> t;
    while (t--) {
        std::cin >> n; len = 0;
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i], l[i] = 0;
            for (int x = a[i]; x > 0; x /= 2)
                dg[i][l[i]++] = x % 2;
            len += l[i];
        }
        if (!len) std::cout << "0\n";
        else {
            for (int i = 1; i <= n; ++i)
                for (int j = l[i]; j <= len; ++j)
                dg[i][j] = 0;
            for (int i = 0; i <= len; ++i) {
                if (i < l[1]) f[1][i] = INF;
                else f[1][i] = i;
            }
            for (int i = 2; i <= n; ++i) {
                for (int x = 0; x <= len; ++x) {
                    for (int y = 0; y <= len; ++y) {
                        if (!x || !y) lcs[x][y] = 0;
                        else if (dg[i - 1][x - 1] == dg[i][y - 1])
                            lcs[x][y] = lcs[x - 1][y - 1] + 1;
                        else lcs[x][y] = std::max(lcs[x][y - 1], lcs[x - 1][y]);
                    }
                }
                for (int x = l[i]; x <= len; ++x) {
                    f[i][x] = INF;
                    for (int y = l[i - 1]; y <= len; ++y)
                        chkmin(f[i][x], f[i - 1][y] + x - lcs[y][x]);
                }
            }
            int ans = INF;
            for (int i = l[n]; i <= len; ++i)
                chkmin(ans, f[n][i]);
            std::cout << ans << "\n";
        }
    }
}