题解 P8108

dead_X · 2022-03-10 21:57:45 · 题解

前言

Cnoi 永远的神！

思路

首先我们考虑只有两列的情况，发现这就是求一个 LCS 的问题：可以一列消一块，或者两列底部相同的时候都消掉。

不难发现推广到 n 列的时候也是对的，这就相当于将一起消掉的多个元素连在一起，连边之间不能有交，答案即为 n^2-\sum f_i，f_i 为第 i 列和第 i+1 列的 LCS。

然后注意到 LCS 问题如果不是排列只能做到 O(n^2) 啊，做 n 次就是 O(n^3) 的，根本过不去，难道这是牛逼论文题？

我们突然发现数据好像是随机的啊，那么这有啥性质呢？

冷静分析一下这和排列也差不多啊，每种颜色只出现了 O(1) 次，将这些相同的 (i,j) 全部记录下来，这就还是相当于一个 O(n) 个点的最长上升子序列，直接做就是 O(n\log n) 的，总时间复杂度 O(n^2\log n)。

代码

// Problem: P8108 [Cnoi2021]绀珠传说
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8108?contestId=46585
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//And in that light,I find deliverance.
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int tree[1003],n=read();
int a[1003][1003];
vector<int> v[1003][1003];
void add(int x,int k)
{
    while(x<=n) tree[x]=max(tree[x],k),x+=x&(-x);
    return ;
}
int find(int x)
{
    int res=0;
    while(x) res=max(res,tree[x]),x-=x&(-x);
    return res;
}
signed main()
{
    for(int j=n; j>=1; --j)
        for(int i=1; i<=n; ++i) 
            v[i][a[i][j]=read()].push_back(j);
    int ans=n*n;
    for(int i=1; i<n; ++i)
    {
        for(int j=1; j<=n; ++j) tree[j]=0;
        int q=0;
        for(int j=1; j<=n; ++j) 
        {
            vector<pair<int,int>> z;
            for(int k:v[i][a[i+1][j]]) 
                z.push_back(make_pair(k,find(k-1)));
            for(auto k:z)
                q=max(q,k.second+1),add(k.first,k.second+1);
        }
        ans-=q;
    }
    printf("%d\n",ans);
    return 0;
}