Dynamic planning question 05_ Missile interception

• Title Description ：
  In order to defend against the missile attack of the enemy , Developing a missile interception system .
  But there's a flaw in this interceptor system ： Although it can intercept missiles at any height , But every time a missile is intercepted , Its interception ability will be reduced to the height that it can only intercept the last intercepted missile .
  One day , The radar caught the enemy's missiles coming , Missiles came in turn , How many missiles can the interception system intercept at most ？
• Input:
  Enter several data ： The altitude at which the missiles fly in turn （ The altitude data given by radar is not greater than 30000 The positive integer , Separate... With spaces ）.
• Output:
  1、 Output the maximum number of missiles this system can intercept .
  2、 Output the number of interception systems needed to intercept all missiles

---

Case input and output ：

• Input：
  3890 2070 1550 3000 2990 1700 1580 650
• Output：
  6
2

---

#include<iostream>
#include<cstring>
using namespace std;
const int MAX = 1025;
int a[MAX],b[MAX],c[MAX];
int i,maxTp;
int n,m,x;

int main()
{
    
    memset(a,0,sizeof(a));  //  Record the Missile Altitude 
    memset(b,0,sizeof(b));  //  Record the maximum non descending sequence length 
    memset(c,0,sizeof(c));

    i = 1;
    m = 0;  //  The maximum number of missiles intercepted by a system 
    n = 0;  //  Number of interception systems required 

    while(cin>>a[i]){
       //  input data 
        maxTp = 0;

        for(int j=1; j<=i-1; j++){
      //  The first i The missile in front of the missile   And  i missile   contrast 
            if((a[j] >= a[i]) && (b[j]>maxTp) )
            maxTp = b[j];
        }
        //  Choose the longest sequence   Connect 
        b[i] = maxTp + 1;   //  add   The first i missiles 

        if(b[i]>m)
            m = b[i]; //  Maximum number of interceptions 

        //  So far, the first question is completed 

        x = 0;  //  In circulation ,x=0, and n May change 
        for(int j=1; j<=n; j++){
    
            if(c[j]>=a[i])
               if(x==0)
                  x = j;
               else
                  if(c[x] > c[j])
                     x = j;
        }

        if(x==0){
      //  There is at least one interception system by default 
            n++;
            x = n;
        }
        c[x] = a[i];

        i++;  //  Prepare for the next missile 
    }

    cout<<m<<endl<<n<<endl;
   return 0;
}