hdu5256|hdu5256 序列变换（最长上升子序列） hdu5256序列变换（最长上升子序

题意： 【hdu5256|hdu5256 序列变换（最长上升子序列）】我们有一个数列A1,A2…An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。
请输出最少需要修改多少个元素。
数据范围：n<=1e5
解法：

容易想到计算最多保留多少个,然后想到最长上升子序列但是题目说了:"无论是修改前还是修改后，每个元素都必须是整数" 例如1 2 1 1 3,我们不能选择1 2 x x 3,因为这样之后两个x就没有数可以修改了,实际上是LIS多了一个限制: 设i j是最长上升子序列的连续部分,那么a[j]-a[i]>=j-i 移项得a[j]-j>=a[i]-i 也就是说我们要求满足a[j]-j>=a[i]-i的最长上升子序列令b[i]=a[i]-i 求b数组的最长非严格上升子序列即可容易证明这样选出的子序列一定满足a[j]-j>=a[i]-i

code：

#include using namespace std; const int maxm=1e5+5; int a[maxm]; int b[maxm]; int stk[maxm]; signed main(){ int T; scanf("%d",&T); int cas=1; while(T--){ int n; scanf("%d",&n); for(int i=1; i<=n; i++){ scanf("%d",&a[i]); b[i]=a[i]-i; } int len=0; for(int i=1; i<=n; i++){ int l=1,r=len; int pos=-1; while(l<=r){ int mid=(l+r)/2; if(stk[mid]>b[i]){//找>b[i]的最左位置 pos=mid,r=mid-1; }else{ l=mid+1; } } if(pos==-1){ stk[++len]=b[i]; }else{ stk[pos]=b[i]; } } printf("Case #%d:\n",cas++); printf("%d\n",n-len); } return 0; }