【BZOJ4282】慎二的随机数列（水题）

点此看题面

大致题意： 给你一个序列，其中有一些元素可以任意填，求最大化严格最长上升子序列长度。

贪心

显然，选择全部任意填的元素一定能得到最优答案。（因为你就算选了一个已知的数，也可以拿任意填的数去替代它）

那我们就把它们先取完，然后考虑剩下这个序列。

我们发现，假如\(i\)和\(j\)之间有\(x\)个任意填的元素，则\(a_j\)需要大于\(a_i+x\)才能同时选择它们两个。

也就是说，设\(s_i\)为前\(i\)个数中任意填的元素个数，那么能同时选\(a_i,a_j\)，就需要满足\(a_j-s_j>a_i-s_i\)。

所以我们直接对\(\{a_i-s_i\}\)这个序列做一次最长上升子序列，再把答案加上任意填的元素个数就可以了。

众所周知最长上升子序列是可以通过二分实现\(O(nlogn)\)的，于是这题就做完了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
using namespace std;
int n,cnt,a[N+5];
I void Ins(CI x)//往最长上升子序列中加一个元素
{
	if(!cnt||x>a[cnt]) return (void)(a[++cnt]=x);//如果大于已有的所有数
	RI l=1,r=cnt,mid;W(l<r) a[mid=l+r-1>>1]>=x?r=mid:l=mid+1;a[r]=x;//二分找到它的位置
}
int main()
{
	RI i,t=0,x;char op;for(scanf("%d",&n),i=1;i<=n;++i)
		cin>>op,op^‘N‘?(scanf("%d",&x),Ins(x-t),0):++t;//t统计当前任意填的元素个数
	return printf("%d",cnt+t),0;//把两个答案加起来输出
}

【BZOJ4282】慎二的随机数列（水题）

原文：https://www.cnblogs.com/chenxiaoran666/p/BZOJ4282.html