自动搬运

查看原文

来自洛谷，原作者为

	哈哈人生 Go Best.

搬运于2025-08-24 23:06:20，当前版本为作者最后更新于2024-11-23 20:30:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话

好久没写题解了，碰巧遇到了这题。
这题挺有意思的。

思路

读完题后，可发现最终答案和不同数字的个数有关，和具体数值无关，所以先把 $a_i$ 离散化。然后考虑动态规划，设 $dp_i$ 表示前 $i$ 个数分段所得的最小值。先写个最简单的思路，易得转移式为 $dp_i=min_{j=0}^{i-1} dp_j+w^2$，其中 $dp_0=0$，$w$ 表示的是 $a_j$ 到 $a_i$ 之间不同数字的个数。对于每个 $i$，从大到小枚举 $j$，顺便用桶记录不同数字的个数，$n^2$ 的做法就被我们找到了，加一个小优化可得 $48$ 分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],dp[200005];
int lsh[200005],tot=0;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],lsh[++tot]=a[i];
	sort(lsh+1,lsh+tot+1);
	tot=unique(lsh+1,lsh+tot+1)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
	for(int i=1;i<=n;i++){
		dp[i]=1e18;
		int w=1;
		b[a[i]]=i;
		for(int j=i-1;j>=0;j--){
			if(w*w>=dp[i])break;//小优化
			dp[i]=min(dp[i],dp[j]+w*w);
			if(b[a[j]]!=i)w++,b[a[j]]=i;
		}
	}
	cout<<dp[n];
	return 0;
}

那这个思路是不是陷入瓶颈了呢？再重新想一下哪些转移位置是真的有用的。设 $dp_i$ 是从某个位置 $j$ 上转移来的，而 $j$ 若满足 $a_{j-1}$ 是在 $a_j$ 到 $a_i$ 中出现过的，那么其显然不如从位置 $j-1$ 上转移，因为多一个已出现的 $a_{j-1}$ 无任何增加的花费，所以此时位置 $j$ 无用，也就是说最优的 $dp_i$ 一定不是从 $j$ 转移过来的。把这个规律普遍化一下，就会发现对于 $dp_i$ 来说，一个位置 $j$ 真正有用就需要满足不存在 $j+1\le k\le i$，使得 $a_k=a_j$。我们可以用一个桶来存所有数字最后出现的位置，再用 set 来维护之间的先后顺序，每次转移都从 set 中所存的位置一一尝试选取最优解。但这样乍一看，set 的大小最多也是 $i$，似乎还是 $n^2$ 的时间复杂度。但别忘了我们还有一个小优化：if(w*w>=dp[i])break;。之前这个优化的作用不明显是因为每个位置可能数字出现过也有可能没出现过，构造特定数据还是能使循环执行接近 $i$ 次。但这回我们每访问 set 中的一个位置，$w$ 必定加一，因为我们存的是每个数字最后一次出现的位置。所以这个代码就使我们的时间复杂度变为 $O(n\sqrt n)$（$dp_i$ 的最大取值也不过是 $i$，而且显然会小很多），并且大概率跑不满。

正解代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],b[200005],dp[200005];
int lsh[200005],tot=0; 
set<int> s;
typedef int type;
inline type read(){
	type x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
inline void write(type x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x / 10);
	putchar(x%10+'0');
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),lsh[++tot]=a[i];
	sort(lsh+1,lsh+tot+1);
	tot=unique(lsh+1,lsh+tot+1)-lsh-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+tot+1,a[i])-lsh;
	for(int i=1;i<=n;i++){
		dp[i]=1e18;
		if(b[a[i]])s.erase(s.find(-b[a[i]]));
		int w=1;
		for(auto it=s.begin();it!=s.end();it++){
			int j=-*it;
			dp[i]=min(dp[i],dp[j]+w*w);
			w++;
			if(w*w>=dp[i])break;
		}
		dp[i]=min(dp[i],w*w);
		b[a[i]]=i,s.insert(-i);//存-i是在使set从大往小排列位置
	}
	write(dp[n]);
	return 0;
}

后记

点个赞吧。