题解：CF1481E Sorting Books

如此费解的题目，我拖了半年才终于搞了出来……

以下设

dp_i

代表把

[i,n]

区间排列整齐的最多可保留的书的数目。通过暴力搜索和肉眼观察可得：每一本书最多移动一次！

转移分为

3

类：

移动这本书： $dp_i=dp_{i+1}$ 。
将所有某种颜色的书之间的其他颜色的书移走：设这个颜色的书的范围为 $[l,r]$ ，出现次数为 $cnt$ （全文余同），转移即为 $dp_l = dp_{r+1}+cnt$ 。
对于任意一堆从后往前（要求是后缀和）的相同颜色的书，可以将其全部置于末尾，之后运用单纯的移动，将所有同色书放在一起： $dp_{i}=cnt$ 。（ $cnt$ 需要动态更新）

时间复杂度

O(n)

。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
	int a=0,b=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		a=(a<<1)+(a<<3)+(c-'0');
		c=getchar();
	}
	return a*b;
}
inline void write(int x){
	if(x<0)	putchar('-'),x=-x;
	if(x>=10)	write(x/10);
	putchar(x%10+48); 
}
inline void write1(int x){
	write(x),putchar(' ');
}
inline void write2(int x){
	write(x),putchar('\n');
}
int n;
int a[5*114514];
int l[5*114514],r[5*114514];
int dp[5*114514];	//倒序 dp  

int cnt[5*114514];
#undef int
int main(){
	#define int long long
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(!l[a[i]])	l[a[i]]=i;
		r[a[i]]=i;
	} 
	for(int i=n;i>=1;i--){
		//枚举的是有多少个元素可以不动？
		dp[i]=dp[i+1];	//代表直接移走？ 
		cnt[a[i]]++;
		dp[i]=max(dp[i],cnt[a[i]]);
		if(l[a[i]]==i){
			dp[i]=max(dp[i],dp[r[a[i]]+1]+cnt[a[i]]);
		} 
//		cout<<'!'<<dp[i]<<endl;
	}
	write2(n-dp[1]);
	return 0;
} //一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

题解：CF1481E Sorting Books

文章操作

相关推荐

评论

题解：CF1481E Sorting Books