题解：P8108 [Cnoi2021] 绀珠传说

zifanwang · 2025-07-10 22:16:44 · 题解

考虑将连续相同的段删除等价于什么，即对所有相邻的两列选择一个公共子序列，对应位置合并一起删除。答案即为 n^2 减去所有相邻两列 LCS 长度之和。

注意到数据是随机生成的，即同一列中每种颜色的出现次数都是 \mathcal O(1) 的，直接枚举匹配的位置树状数组维护转移即可。

时间复杂度 \mathcal O(n^2\log n)。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 1003
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int n,ans,f[mxn],a[mxn][mxn];
vector<int>s[mxn];
inline void upd(int x,int y){
    for(;x<=n;x+=x&-x)f[x]=max(f[x],y);
}
inline int ask(int x){
    int s=0;
    for(;x;x-=x&-x)s=max(s,f[x]);
    return s;
}
signed main(){
    scanf("%d",&n),ans=n*n;
    rep(i,1,n)rep(j,1,n)scanf("%d",&a[j][i]);
    rep(i,2,n){
        rep(j,1,n)s[j].clear(),f[j]=0;
        drep(j,n,1)s[a[i-1][j]].pb(j);
        rep(j,1,n){
            for(int x:s[a[i][j]]){
                upd(x,ask(x-1)+1);
            }
        }
        ans-=ask(n);
    }
    cout<<ans;
    return 0;
}