[cf] Codeforces Round #793 (Div. 2) C. LIS or Reverse LIS?

前言

t a g : tag : tag: LIS 思维 贪心 排序 传送门 :

题意 : 给定一个数组 a [ ] a[] a[],对于该数组的价值是 m i n ( L I S ( a ) , L I S ( a ′ ) ) min(LIS(a),LIS(a')) min(LIS(a),LIS(a′)), a ′ a' a′是 a a a的翻转数组

现在你可以任意排列 a a a,询问最大的价值是多少

思路 : 显然因为取 m i n min min的关系, L I S ( a ) LIS(a) LIS(a)与 L I S ( a ′ ) LIS(a') LIS(a′)相互约束,因此只有他们一半一半的时候才是最大的

因此我们只需要统计出数组中只出现一次的数的个数,那么我们就知道 m i n ( L I S ( a ) , L I S ( a ′ ) ) = ( c n t + 1 ) / 2 min(LIS(a),LIS(a'))=(cnt+1)/2 min(LIS(a),LIS(a′))=(cnt+1)/2,因为他们可以共用一个端点,所以我们上取整

最后在加上出现次数为 > = 2 >=2 >=2的,这样子每边都可以放一个,即得答案

code :

void solve(){
	cin>>n;
	mp.clear();
	
	for(int i = 1;i>a[i],mp[a[i]]++;
	
	int res = 0 ;
	int rm = 0 ;

	for(auto it : mp){
		if(it.y >= 2)rm ++ ;
		else if(it.y == 1) res++;
	}
	
	res = (res+1)/2;
	res += rm;
	cout