HDU 4521小明系列问题——小明序列(二分查找,LIS)

时间:2023-01-14 19:31:50

这篇博客的内容基本上都是观看一位大佬博客所得,所以内容基本一致,写下这篇博客也只是为了总结自己学习的收获。

贴一下大佬博客:https://blog.csdn.net/a709743744/article/details/51765252

题目要求:给一段序列a,求满足每个元素在原序列里位置至少相隔k的最长上升子序列。

这道题可以用求最长上升子序列类似的方法求,最普通的最长上升子序列二分求法是开一个b数组储存最长上升子序列(不是真正的最长上升子序列),然后遍历a数组,对于a数组里面的每一个元素我们查找b数组里面第一个大于它的元素的位置,然后替换,如果没有大于它的元素,则插入到b数组中的末尾位置,不断维护(如果不懂的可以去看我另一篇讲最长上升子序列的博客)。对于这道题,我们需要稍微变换一下,我们需要再开一个数组c来储存b数组每一次更新时的位置,然后,当前只更新i-k之前的那个数,这样子就能保证b数组里的所有数都至少比当前数位置少k。

具体看代码:

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f;
typedef long long LL;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int maxn=1e5+9;
int a[maxn],b[maxn],c[maxn];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,n;
	while(cin>>n>>k){
		int len=0;
		for(i=0;i<n;i++)b[i]=inf;
		for(i=0;i<n;i++){
			cin>>a[i];
			int x=lower_bound(b,b+len,a[i])-b;
			c[i]=x;
			if(x==len)len++;
			int j=i-k;
			if(j>=0&&b[c[j]]>a[j])b[c[j]]=a[j];
		}
		cout<<len<<endl;
	}
}