1260：【例9.4】拦截导弹(Noip1999)

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1005;
 4 int main(){
 5     int t,r=0,cnt=0,maxx=0,k[n],a[n],b[n];
 6     while(cin>>t){
 7         //第一问：dp
 8         a[++cnt]=t;
 9         b[cnt]=1;//初始化
10         for(int i=1;i<cnt;i++)
11             if(a[i]>=a[cnt])b[cnt]=max(b[i]+1,b[cnt]);
12         maxx=@H_308_12@max(maxx,b[cnt]);
13         //遍历已有的拦截系统，选择代价最小的进行拦截，实在拦截不了就再添加一个拦截系统
14         int mi=30*N,s;
15         for(int i=0;i<r;i++){
16             if(t<=k[i]){
17                 if(mi>k[i]-t){
18                     mi=k[i]-t;
19                     s=i;
20                 }
21             }
22         }
23         if(mi<30*N)k[s]=t;
24         else k[r++]=t;
25     }
26     cout<<maxx<<"n"<<r;
27     return 0;
28 }