题解 P1020 【导弹拦截】

###似乎可以不用DP来做，下面用了一个二分查找+贪心 ```cpp #include<bits/stdc++.h> using namespace std; int a[21],b[21],h[21],as,bs=1,hs,ns1; inline int upper(int size,int key){//二分查找的复杂度是O(logn)的，实际上比DP快一些（尽管数据不卡时间） int s=1,t=size,pos,mid; while((s<t)&&(mid=(s+t)>>1)) if(b[mid]<=key) pos=t=mid; else pos=s=mid+1;//不断二分，找到第一个比key大数，也就意味着前面的 if(!pos) return 1;//数都比这个数大，后面的数都比这个数小。这里有特判，目的是防止当b数组只有一个数时插入到pos=0 return pos; } int main(){ while(scanf("%d",&a[++as])!=EOF){//在线处理 if(as==1) b[1]=a[1];//初始化，为了使后面进来的数可以插入 else if(a[as]<=b[bs]) b[++bs]=a[as];//这里要求最长不上升子序列，所以当遇到一个比当前更小的数就直接放在末尾 else b[upper(bs,a[as])]=a[as]; ns1=0;//这里的贪心法则是：我们一开始有一套系统，拦截第一枚导弹，检查不断来的导弹，如果没有能拦截的，就新建系统，否则找 for(int i=1;i<=hs;i++) if((h[i]>=a[as])&&((!ns1)||(ns1&&h[i]<h[ns1]))) ns1=i;//可拦截切高度最低的系统拦截，简单证明：有系统A1,A2， if(!ns1) ns1=++hs;//高度H1,H2，当有高度H1>H2>H的导弹过来时，如果我们用A1来拦不符合贪心法则，如果又有一枚H1>H4>H2的 h[ns1]=a[as];//导弹过来，那么A1,A2都将失效，所以系统数要++，而在其他情况下要么都可拦截，要么都不可拦截，对选择不影响 ``` }//因此该贪心策略最优 printf("%d\n%d",bs,hs);//当然第二问还可以求最长不下降子序列来求解 }