/* 求严格最长递减序列。  // 1: a[i] > stack[top]  非严格最长递减序列。(最长非递增序列) a[i] < stack[top]  非严格最长递增序列。 (最长非递减序列) a[i] <= stack[top]  严格最长递增序列。  其他不变 */  #include 
     
       using namespace std; int stack[5008],a[5008]; int main() {     int temp,temp2;     int n = 1;     int cases = 1;          while(scanf("%d",&temp) != -1)     {         if(temp == -1)             break;         a[n ++] = temp;         while(scanf("%d",&temp2) != -1 && temp2 != -1)         {             a[n ++] = temp2;         }         stack[1] = a[1];         int max = 1,top = 1,i;         for(i=2 ;i
      
       = stack[top] && top>= 1) // 1                 top --;             stack[top+1] = a[i];             top ++;             if(max < top)                 max = top;             else                 top = max;         }         printf("Test #%d:\n  maximum possible interceptions: %d\n\n",cases ++,max);         n = 1;     }     return 0; } /* //O(n^2) 较好操作 #include 
       
         using namespace std; int dp[5001],a[5001]; int main() {     int temp,temp2;     int n = 1;     int cases = 1;          while(scanf("%d",&temp) != -1)     {         if(temp == -1)             break;         a[n ++] = temp;         while(scanf("%d",&temp2) != -1 && temp2 != -1)         {             a[n ++] = temp2;         }         memset(dp,0,sizeof(dp));         int max = 1,top = 1,i,j;         for(i=1 ;i
        
         =1 ;j--)  // 往回找a[j] > a[i] && dp[i] < dp[j] + 1             {                 if(a[j] > a[i] && dp[i] < dp[j] + 1)                      dp[i] = dp[j] + 1;                 if(max < dp[i])                 {                     max = dp[i];                 }              }          }         printf("Test #%d:\n  maximum possible interceptions: %d\n\n",cases++,max);         n = 1;     }     return 0; } */ //其他思路：http://www.slyar.com/blog/longest-ordered-subsequence.html