P11311 解题报告

前言

怎么蓝了，那就写篇题解吧。

思路分析

套路地，设

f_i

表示到第

i

位的最小答案，易得转移：

f_i=f_j+cal(j+1,i)^2,j<i

其中

cal(l,r)

表示区间

[l,r]

的不同颜色种类数。

~~然后你大胆猜测有决策单调性，大力二分队列维护就做完了。~~

注意到答案上界为

n

，也就是把序列断成

n

段，每段代价为

1

。

因此，我们的合法转移区间

[j+1,i]

，其中的颜色种类数必然

\le \sqrt{n}

。

使用刷表法转移。考虑用一个链表记录当前每种颜色下一次出现的位置，用 set 维护这些位置。每次转移时，只需要转移 set 中当前颜色的

\sqrt{n}

个后继就行了。

不难发现复杂度是

O(n\sqrt{n}\log n)

的，感谢良心出题人没有卡 set 的巨大常数。

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],b[200005],pre[200005],suf[200005],f[200005],vis[200005];
set<int> s;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int cnt=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	}
	for(int i=1;i<=n;i++){
		suf[pre[a[i]]]=i;
		pre[a[i]]=i;
	}
	s.insert(n+1);
	for(int i=1;i<=n;i++){
		if(!vis[a[i]]) s.insert(i); 
		vis[a[i]]=1;
	}
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		set<int>::iterator it=s.begin();
		it=next(it);
		for(int j=1;j*j<=n && it!=s.end();j++,it=next(it)){
			f[(*it)-1]=min(f[(*it)-1],f[i-1]+j*j);
		}
		s.erase(i);
		if(suf[i]){
			s.insert(suf[i]);
		}
	}
	cout<<f[n];
	return 0;
}

题解：P11311 漫长的小纸带

文章操作

P11311 解题报告

前言

思路分析

代码实现

相关推荐

评论

题解：P11311 漫长的小纸带