【杭电】[5256]序列变换

问题描述

问题分析

考虑序列限制条件为a[i]-a[j]>=i-j

a[i]-i>=a[j]-j

所以考虑建数组b[i]=a[i]-i

则问题转换为求数组b[i]的不递减序列的长度l

则最后结果为n-l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <stdio.h>
int inf=99999999;
int n,l;
int a[100200];
int s[100200];
int find(int m) {
	int la=0,lb=l;
	while(lb>=la) {
		int mid=(la+lb)>>1;
		if(s[mid]>m)
			lb=mid-1;
		else
			la=mid+1;
	}
	return la;
}
int main() {
	int T,kase=0;
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&n);
		for(int i=1; i<=n; i++) {
			int t;
			scanf("%d",&t);
			a[i]=t-i;
		}
		s[0]=-inf;
		l=1;
		for(int i=1; i<=n; i++) {
			s[l]=inf;
			int t=find(a[i]);
			if(t==l)
				l++;
			s[t]=a[i];
		}
		printf("Case #%d:\n",++kase);
		printf("%d\n",n-l+1);
	}
	return 0;
}