1883: Sequence Number

Time Limit: 1 Sec     Memory Limit: 1280 MB Total Submissions: 20     Accepted: 6 [ Submit]   [ Statistic]   [ Go Back]

题目描述

     In Linear algebra, we have learned the definition of inversion number:

    Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each other. If exist positive integers i , j, ( 1 ≤ i ＜ j ≤ n and A[i] ＞ A[j]), <A[i], A[j]> is regarded as one of A’s inversions. The number of inversions is regarded as inversion number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>, <6,1>,and the inversion number is 5.

     Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1 ≤ i ≤ j ≤ n and A[i]  <=  A[j], <A[i], A[j]> is regarded as one of A’s sequence pair. The number of sequence pairs is regarded as sequence number. Define j – i as the length of the sequence pair.

     Now, we wonder that the largest length S of all sequence pairs for a given array A. 

输入描述

    There are multiply test cases.

    In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array, the 2th ~n+1th line are one number per line, indicates the element Ai （1<=Ai<=10^9） of the array.  

输出描述

 Output the answer S in one line for each case. 

输入样例

5 2 3 8 6 1

输出样例

3

AC代码如下：

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int maxn=1e5+10; int a[maxn]; int main() { int n,maxi; while(cin>>n) { maxi=0; for(int i=0;i<n;i++) cin>>a[i]; for(int i=n-1;i>=0;i--) { for(int j=0;j+i<n;j++) { if(j<i && a[j]<=a[i+j]) { maxi=max(maxi,i); i=-1;j=n;//退出多重循环 break; } } } cout<<maxi<<endl; } return 0; }