[BZOJ5427]最长上升子序列/[BZOJ4282]慎二的随机数列

题目大意：

给你一个长度为\(n(n\le10^5)\)的整数序列，其中有一些数已经模糊不清了，现在请你任意确定这些整数的值，使得最长上升子序列最长。求最长长度。

思路：

一定存在一种最优方案使得不确定的都选上（考虑新选上一个不确定的数，最多会使一个已确定的数失效），因此令\(a_i=a_i-cnt\)（\(cnt\)为之前不确定的数的个数），求LIS后加上\(cnt\)即可。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

inline char getupper() {

	register char ch;

	while(!isupper(ch=getchar()));

	return ch;

}

const int N=1e5+1;

int a[N],tmp[N];

class FenwickTree {

	private:

		int val[N];

		int lowbit(const int &x) const {

			return x&-x;

		}

	public:

		void modify(int p,const int &x) {

			for(;p<=tmp[0];p+=lowbit(p)) {

				val[p]=std::max(val[p],x);

			}

		}

		int query(int p) const {

			int ret=0;

			for(;p;p-=lowbit(p)) {

				ret=std::max(ret,val[p]);

			}

			return ret;

		}

};

FenwickTree bit;

int main() {

	const int n=getint();

	int cnt=0;

	for(register int i=1;i<=n;i++) {

		if(getupper()=='K') {

			a[i]=tmp[i-cnt]=getint()-cnt;

		} else {

			a[i]=INT_MAX;

			cnt++;

		}

	}

	std::sort(&tmp[1],&tmp[n-cnt]+1);

	tmp[0]=std::unique(&tmp[1],&tmp[n-cnt]+1)-&tmp[1];

	for(register int i=1;i<=n;i++) {

		if(a[i]==INT_MAX) continue;

		a[i]=std::lower_bound(&tmp[1],&tmp[tmp[0]]+1,a[i])-tmp;

		bit.modify(a[i],bit.query(a[i]-1)+1);

	}

	printf("%d\n",bit.query(tmp[0])+cnt);

	return 0;

}

巴特西

[BZOJ5427]最长上升子序列/[BZOJ4282]慎二的随机数列

[BZOJ5427]最长上升子序列/[BZOJ4282]慎二的随机数列

题目大意：

思路：

源代码：

最新文章

热门文章