【题解】Luogu P1020【导弹拦截】

这里Luogu居然加强数据,O(n^{2})算法居然不能拿满200分,,,不过100分也算√,所以O(n \log n)算法后面再补

第一问就是经典的最长不下降子序列问题,第二问贪心。

#include<cstdio>

const int MAXN = 100000 + 6;

int A[MAXN],b[MAXN],h[MAXN];

int main(){
	int n = 1;
	
	while(scanf("%d",&A[n]) != EOF){
		n++;
	}
	n--;
	
	int max = 0,m = 0,x = 0,ans = 0;
	for(int i = 1;i <= n;i++){
		max = 0;
		for(int j = 1;j <= i - 1;j++){
			if(A[j] >= A[i]){
				if(b[j] > max){
					max = b[j];
				}
			}
		}
		b[i] = max + 1;
		
		if(b[i] > m){
			m = b[i];
		}
		
		x = 0;
		for(int j = 1;j <= n;j++){
			if(h[j] >= A[i]){
				if(x == 0){
					x = j;
				}else if(h[j] < h[x]){
					x = j;
				}
			}
		}
		if(x == 0){
			ans++;
			x = ans;
		}
		h[x] = A[i];
	}
	
	printf("%d\n%d",m,ans);
	
	return 0;
}

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注