如果你用二分,并且没有200分,看这里
查看原帖
如果你用二分,并且没有200分,看这里
755251
adidde楼主2023/1/28 18:19

求最长不上升子序列: 因为导弹的高度可以重复,所以不用判重,在修改dp(找第一个小于x的数) 二分这么写:

int solve(int l,int r,int x){
	while(l<r){
		int mid = (l+r)>>1;
		if(dp[mid]<x)
			r = mid;
		else
			l = mid+1;
	}
	return l;
}

求最长不下降之序列: 这里要判重(高度相同,可以看作是一个系统),在修改dp时(找第一个大于等于x的数) 二分这么写:

int solve2(int l,int r,int x){
	while(l<r){
		int mid = (l+r)>>1;
		if(dp2[mid]>=x)
			r = mid;
		else
			l = mid+1;
	}
	return l;
}
2023/1/28 18:19
加载中...