View Code of Problem 1037

#include<iostream>
#include<string.h>
#define size 5010
using namespace std;
int main()
{
    int n;
    int opt[size],price[size],count[size];
    int vis[size];
    int max,ans;
    while(scanf("%d",&n)!=EOF)
    {
       memset(opt,0,sizeof(opt)); 
       memset(vis,0,sizeof(vis));
       ans=max=0;
       for(int i=0;i<n;i++) {scanf("%d",&price[i]); count[i]=1;}
       for(int i=0;i<n;i++)
       {
          // for(int j=0;j<i;j++)
           for(int j=i-1;j>=0;j--) //-------注释① 两个不同循环的区别 
           {  
/*
   opt[j大] < opt[j小],但count[j大]覆盖了count[j小]
   如果是第一个循环，下面标记①处，会重复计算 
*/ 
               if(price[j]>price[i] && !vis[j])
               {
                   if(opt[j]+1>opt[i] ) opt[i]=opt[j]+1 , count[i]=count[j]; 
                   else if(opt[j]+1==opt[i]) // -------① opt[i]改变 
                   count[i]+=count[j];  
               } 
               if(price[j]==price[i]) //------注释②
/*
  下面if(!opt[i])判断,是指price[i]=price[j]情况下(j<i)，若price[j~i-1]中没有使opt[i]>opt[j]
  的情况，则说明0~i与0~j的情况是相同的，即重复的，所以可以标记vis[i]=1，避免重复。 
*/               
               {
                    if(!opt[i])  vis[i]=1; 
                    break;
               }
           } 
           if(opt[i]>max) max=opt[i]; 
       }
       //for(int i=0;i<n;i++) cout<<count[i]<<" ";cout<<endl;
       max++;
       for(int i=0;i<n;i++) 
       if(opt[i]+1==max)  ans+=count[i];
       printf("%d %d\n",max,ans);
    }
    return 0;
}