急急急,脑回路稍微有点清奇,有少量注释,求助70分,蒟蒻求助
查看原帖
急急急,脑回路稍微有点清奇,有少量注释,求助70分,蒟蒻求助
289026
Luna_mili楼主2020/10/26 08:39

希望能在我的代码上指出错误,谢谢

(用了此题没什么用的优化方案)

(我不会告诉你们是因为我懒得重写)

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int t[100010];
int fun(int n){//包装成了函数 
	int dp[100010];
	int len=1;
	dp[1]=a[1];
	for(int i=1;i<=n;i++){
		if(a[i]>dp[len]){
			len++;
			dp[len]=a[i];
		}else{
			int l=1,r=len,ans;
			while(l<=r){
				int mid=(l+r)/2;
				if(dp[mid]>=a[i]){
					ans=mid;
					r=mid-1;
				}
				else{
					l=mid+1;
				}
			}
			dp[ans]=a[i];
		}
	}
	return len;//返回最长上升子序列的长度 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
	}
	int maxx=-1;
	int ans1;
	int ans2;
	for(int ti=2;ti<n;ti++){
		for(int i=1;i<=ti;i++){
			a[i]=t[i];//同下 
		}
		ans1=fun(ti); 
		for(int i=n,j=0;i>=ti;i--,j++){
			a[j]=t[i];//包装a数组 
		}
		ans2=fun(n-ti);
		maxx=max(ans1+ans2-1,maxx);//含有重复因子
	}
	cout<<(n-maxx);
	return 0;
}
//phigros
2020/10/26 08:39
加载中...