求最长不上升子序列:
因为导弹的高度可以重复,所以不用判重,在修改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;
}