自动搬运

查看原文

来自洛谷，原作者为

	程雅馨 没有时间学习的人，是有了时间也不会学习的人

搬运于2025-08-24 21:43:10，当前版本为作者最后更新于2019-10-05 16:59:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$\color{blue}\text{蓝色蒟蒻从哥哥那里得来一个简单的优化办法（表述有些问题请原谅）}$

在题目中可以得出：

只用找一次最长不上升序列 再找一次最长不下降序列 记录下长度 用总数减去较大的那个就好了

代码也很简单：

#include<iostream>
#include<cmath>
using namespace std;
int n,s,a[30005],f[30005],f1[30005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>=a[j])
			f[i]=max(f[i],f[j]);
		}
		f[i]++;
	}//最长不下降序列
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]<=a[j])
			f1[i]=max(f1[i],f1[j]);
		}
		f1[i]++;
	}//最长不上升序列
	for(int i=1;i<=n;i++){
		s=max(s,f[i]);
		s=max(s,f1[i]);
	}//取最长
	cout<<n-s;
	return 0;
}

$\color{blue}\text{但是就这样交上去会超时}$

仔细观察（也不用很仔细） 就能发现卡片上的数字只有$1 2 3$，重复率非常高

于是 可以将内层倒序循环 如果找到数字相同那么前面就不用找了 因为前面已经处理过了

#include<iostream>
#include<cmath>
using namespace std;
int n,s,a[30005],f[30005],f1[30005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>0;j--){
			if(a[i]>=a[j])
			f[i]=max(f[i],f[j]);
			if(a[i]==a[j])break;//前面已经被处理过可以跳过
		}//内层倒序循环
		f[i]++;
	}//最长不下降序列
	for(int i=1;i<=n;i++){
		for(int j=i-1;j>0;j--){
			if(a[i]<=a[j])
			f1[i]=max(f1[i],f1[j]);
			if(a[i]==a[j])break;
		}
		f1[i]++;
	}//最长不上升序列
	for(int i=1;i<=n;i++){
		s=max(s,f[i]);
		s=max(s,f1[i]);
	}
	cout<<n-s;
	return 0;
}

补一句：

这个方法最长不上升序列、最长不下降序列、最长上升序列、最长下降序列都可以用，但数据重复率较高的效果更明显一些。