HDU - 1257 最少拦截系统

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2

• 题解1：我们可以创建一个创建一个数组，在个数组表示当下系统所能达到的最高高度。因此，每出现一个新的炮弹，便在这个数组里找是否能够把这个炮弹打下来的系统，如果存在，就找到那个高度最低的那个系统（保证剩下的系统尽可能存在能打高度的系统），不过不存在，就扩大这个数组。这里要说明的是我们可以发现炮弹系统的数组是递增的，因此，这里可以直接用二分查找便可。最大时间复杂度O（nlog n）.

#include<bits/stdc++.h>
using namespace std;
const int INF = 1<<30;
int sn[100000];
int main()
{int n;while(cin>>n){int t=1;sn[0]=INF;for(int i=0;i<n;i++){int m;cin>>m;int l=lower_bound(sn,sn+t,m)-sn;//cout<<l<<endl;if(l==t){t++;sn[t-1]=m;}else sn[l]=m;}cout<<t<<endl;}
}

• 题解2：dp解决，dp存储的是当下位置时的炮弹所需的系统。这里我们i遍历外层的炮弹，然后内层j我们遍历dp数组，然后比较之前的炮弹，只如果存在sn[j]<sn[i]的话，那就说明系统dp[j]在位置j就已经打在了小于i位置的高度了，因此，不能位置i的系统至少要用dp[j]+1的系统去打了，所以，只需找到最大的那个dp[j]+1填到位置i的dp就行了

#include<bits/stdc++.h>
using namespace std;
const int inf = 1e5;
int sn[inf],dp[inf];
int main()
{int n;while(cin>>n){for(int i=0;i<n;i++){cin>>sn[i];dp[i]=1;}for(int i=0;i<n;i++)for(int j=0;j<i;j++){if(sn[j]<sn[i]){dp[i]=max(dp[i],dp[j]+1);}}int ans=0;for(int i=0;i<n;i++)ans=max(ans,dp[i]);cout<<ans<<endl;}return 0;
}