點(diǎn)擊打開鏈接

思路：

lis的變形，唯一不同的是條件a[i] - i > a[j] - j + 1,i>j。因?yàn)橐_保這兩個(gè)元素之間能插入i - j + 1個(gè)元素

每個(gè)數(shù)先減去它的下標(biāo)，防止下面的情況發(fā)生：加入序列是1,2,2,2,3,這樣求上升子序列是3，也就是要修改2個(gè)，但是中間的兩個(gè)2，變化范圍又不能超過（1,3）那么這樣求的也就不對(duì)，但是減掉之后，相當(dāng)于給中間重復(fù)的數(shù)留下了修改的空間解釋下為什么可以減而保持正確性：因?yàn)轭}目所求時(shí)嚴(yán)格遞增，假設(shè)是2，3, 4，那么變成1, 1, 1，所以在LIS里非嚴(yán)格遞增就可以了這也是為什么要在upper_bound的位置插入另外：lower_bound返回第一個(gè)>=key的位置；upper_bound返回第一個(gè)>key的位置，這樣相減才是key的個(gè)數(shù)
求嚴(yán)格遞增的LIS的方法(非嚴(yán)格遞增的LIS只要把lower_bound改成upper_bound)
		memset(b,0x3f,sizeof(b));		int mx = -1;		for(int i=1; i<=n; i++){			int pos = lower_bound(b+1,b+1+n,a[i])-b;			b[pos] = a[i];			mx = max(mx,pos);		}
代碼：
#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+10;int n,a[maxn],b[maxn];// int dp(){// 	int len=1;// 	b[1] = a[1];// 	for(int i=2; i<=n; i++){// 		if(a[i]>=b[len]){// 			len++;// 			b[len] = a[i];// 		}else{// 			int pos = upper_bound(b+1,b+len,a[i])-b;// 			b[pos] = a[i];// 		}// 	}// 	return len;// }int main(){	int T; scanf("%d",&T);	for(int cas=1; cas<=T; cas++){		scanf("%d",&n);		for(int i=1; i<=n; i++){			scanf("%d",&a[i]);			a[i] -= i;		}		memset(b,0x3f,sizeof(b));		int mx = -1;		for(int i=1; i<=n; i++){			int pos = upper_bound(b+1,b+1+n,a[i])-b;			b[pos] = a[i];			mx = max(mx,pos);		}		int ans = n-mx;		PRintf("Case #%d:/n%d/n",cas,ans);		// int ans = n-dp();		// printf("Case #%d:/n%d/n",cas,ans);	}}