【HDU 1257】最少拦截系统 DP or 贪心 详解

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

思路：

样例很具有误导性啊。一种很容易产生的直观误解是：贪心，当前遇到一个比一个小的就继续，代表在一个拦截系统里面，然后遇到一个比前一个大的就开一个新的拦截系统。这样是必WA的，原因是这个贪心还不够贪。如图（表示每个高度）：

按照上述贪心应该是输出3。然而只需要2个拦截系统即可，图中不同颜色代表不同拦截系统拦截的高度。
把这个反例的思路翻译一下就是，我们更优的贪心策略是遇到一个新的导弹，我们看看前面已有的系统中有没有最小值大于等于当前高度的，如果有，就不需要新开，就利用前面的即可。如图中第五颗导弹，他的高度可以利用第一个系统拦截（因为第一个的最小值都比这个大）。若有多个最小值大于当前的，那就再贪心地取最小值最小的，充分利用。而如果前面已有的拦截系统最小值都已经比当前的小了，那就只好新开了。所以每次遇到一个导弹，就往前找已有的拦截系统。这个是O（n²）的时间复杂度。

还有一种更为简单的思路就是直接DP，求一个最长上升子序列LIS。为什么？其实，在这个LIS中，每个元素的高度都代表着前面说的——它所在的拦截系统的最小值（看成最大最小值都行），就像前面贪心策略里面当前这一个的已经不能再放到已有的系统中了（最小值比当前还小）。这就是为什么要求一个最长上升子序列。然后用二分优化一下，时间复杂度O（nlogn），个人觉得这个方法更巧妙一些。

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 1e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){return x&(-x);}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} };ll dp[maxn];
ll len[maxn];
vector<ll> a;int main()
{ll n ;while(cin>>n){a.clear();mem(dp,0);rep(i,1,n){ll x = read();a.pb(x);}int maxlen = 0;  len[maxlen] = 0;int ma = -1;rep(i,0,n-1){if(a[i]>len[maxlen]) len[++maxlen] = a[i], dp[i] = maxlen;else{int idx = lower_bound(len+1,len+1+maxlen, a[i]) - len;len[idx] = a[i];dp[i] = idx;}ma = max(ma,dp[i]);}cout<<ma<<endl;}return 0;
}