题解：AT_arc219_f [ARC219F] Range Division

· · 题解

约定 m=O(\log V)。

考虑如下问题：

给定 n 个字符串 s_i，每次可以选择区间 [l,r] 都不是空串且满足 s_l,\cdots,s_r 的末尾字符都一样，并删去末尾字符，消耗代价为 1，问最小的代价把所有 s_i 变成空串。

关键结论：答案为 \sum_{i=1}^n|s_i|-\sum_{i=1}^{n-1}\text{lcs}(s_i,s_{i+1})，其中 \text{lcs} 表示最长公共子序列。

证明：考虑构造最长公共子序列，设 s_i 与 s_{i+1} 的最长公共子序列的第 j 项在 s_i 是 p_{i,j}，在 s_{i+1} 是 q_{i,j}。

每次删去一个字符，显然需要先删除 (i,j+1)，然后递归的将 (i+1,q_{i+1,j}) 和 (i-1,p_{i-1,j}) 删去。

因此考虑建图，连边 (i,j)\to (i,j+1)，连边 (i,p_{i,j})（双向边）。

这对应把图上所有可达的点都标记，这显然不会标记到 (i,k)(k<j)，因为如果会，由于每个点在一行只会往后连，那一定会有两条相交的边（换言之，存在边 (i,x_1)\to (i+1,y_1),(i,x_2)\to (i+1,y_2)(x_1<x_2) 满足 y_1>y_2，这违背了 LCS 的定义）。

（这里其它题解的证明都非常简洁，可能其实很 trivial？）。

考虑若规定不能选包含 0 的位置操作，将 a_i 转成二进制串 s_i，则就是上述问题。由于 0 可以参与操作，可以看作可以选择给 s_i 补 c_i 个 0，最小化 \sum_{i=1}^n|s_i|+c_i-\sum_{i=1}^{n-1}\text{lcs}(s_{i}0^{c_i},s_{i+1}0^{c_{i+1}})，由于 c_i\le nm，显然考虑 DP，设 f_{i,j} 表示考虑了 s_1\sim s_i，c_i=j 对应的最小代价，朴素转移即可做到 O(n^3m^2)，足以通过。

#include<bits/stdc++.h>
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define down(i,l,r) for(int i=(l);i>=(r);--i)
#define pi pair<int,int>
#define p1 first
#define p2 second
#define m_p make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
inline ll read(){
    ll x=0;short t=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*t;
}
const int m=60;
int n,len[35];ll a[35];
int lcs[2105][2105],dp[35][2005];
void slv(){
    n=read();up(i,1,n)a[i]=read(),len[i]=a[i]?__lg(a[i])+1:0;
    up(i,0,n*m)dp[1][i]=len[1]+i;
    up(i,2,n){
        memset(dp[i],0x3f,sizeof(dp[i]));
        auto g=[&](int p,int x){if(p<=len[x])return (a[x]>>p-1)&1;return 0ll;};
        memset(lcs,0,sizeof(lcs));
        up(j,1,n*m+len[i-1])
            up(k,1,n*m+len[i])
                lcs[j][k]=max(max(lcs[j][k-1],lcs[j-1][k]),lcs[j-1][k-1]+(g(j,i-1)==g(k,i)));
        up(j,0,n*m)up(k,0,n*m)
            dp[i][k]=min(dp[i][k],dp[i-1][j]+len[i]+k-lcs[j+len[i-1]][k+len[i]]);
    }
    int res=1e9;
    up(i,0,n*m)res=min(res,dp[n][i]);
    printf("%d\n",res);
}
int main(){
    // freopen("1.in","r",stdin),freopen("1.out","w",stdout);
    int t=read();while(t--)slv();
    return 0;
}