自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:36:04，当前版本为作者最后更新于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;
}