最少拦截系统优化

Problem Description

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

题目思路：只要不被误会成贪心，直接整就行。
大概就是把每一个系统的存下来，遇到递减序列就过，碰到单的从第一个系统试，不行就加系统。
唯一坑点是if判断不能放在子循环内，不然加不到。。。我就这样想了半天

#include <bits/stdc++.h>
using namespace std;
const int N=100007;
int t,c,i,j;
int a[N];
int dp[N];
int main() {
	while(cin>>t) {
		if(t==-1)break;
		memset(dp,0,sizeof dp);
		for(i=0; i<t; i++) {
			cin>>a[i];
		}
		dp[0]=a[0];
		c=1;
		for(i=1; i<t; i++) {
			for(j=0; j<c; j++) {
				if(dp[j]>=a[i]) {
					dp[j]=a[i];
					break;
				}
			}
				if(j>=c) {
					dp[j]=a[i];
					c++;
				}
		}
		cout<<c<<endl;
	}
	return 0;
}

也可以用最长上升子序列来做-

#include<bits/stdc++.h>
using namespace std;
#define N 300005
int dp[N],a[N];
int main(){
    int t,n;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++) cin>>a[i];
        fill(dp,dp+n+1,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(a[j]<a[i]) dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        cout<<*max_element(dp,dp+n+1)<<endl;
    }
    return 0;
}

上面这个是n*n的复杂度，二分+队列优化过是nlog（n）
贴一个图解

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 100005;
int sz[maxn],tp[maxn]; //
int n=1;
int p=1;
int main(){
	while(cin>>sz[n]) n++;
	tp[1] = sz[1];
	for(int i=2;i<n;i++){
		if(sz[i] <= tp[p]) tp[++p] = sz[i];//注意<= 最长不上升 
		else{
			int l=1,r=p,mid=p>>1;
			while(l!=r){
				if(sz[i] > tp[mid]) r = mid;
				else l = mid+1;
				mid = (l+r)>>1;
			}
			tp[l] = sz[i];
		}
	}
	cout<<p<<endl;
	memset(tp,0,sizeof(tp));
	tp[1]=sz[1];
	p=1;
	for(int i=2;i<=n;i++){
		if(sz[i] > tp[p]) tp[++p] = sz[i];
		else{
			int l=1,r=p,mid=p>>1;
			while(l!=r){
				if(sz[i] <= tp[mid] ) r = mid;
				else l = mid+1;
				mid = (l+r)>>1;
			}
			tp[l] = sz[i];
		}
	}
	cout<<p<<endl;
	return 0;
}