HLG 1597(最長飛遞增子序列)

 

題意：

 

Description 給一個長度為n的整數序列A0,A1,......An-1,找出最長的非遞增子序列的長度 Input

輸入第一行為數據組數T(T<=20)。

每組數據的第一行為整數的個數n(2<=n<=1000)，第二行為n個絕對值不超過150000的整數。

Output 對於每組數據，輸出最長的非遞增子序列的長度。 Sample Input 2
3
1 1 3
4
-1 4 3 2 Sample Output 2
3 解析：

 

這類都是屬於序列問題，不過常見的就是最長單調子序列，這裡只是換了一下，不過方法都還是一樣的；

 

 

#include 
#include 
#include 
#define MAXN 1000+10

int a[MAXN], x[MAXN];

int main()
{
    int n, cas;
    scanf(%d, &cas);

    while(cas--){
        memset(x, 0, sizeof(x));
        scanf(%d, &n);
        for(int i=0; i=0; j--) {
                if(a[j] >= a[i]) {
                    if(x[j]+1 > x[i]) x[i] = x[j]+1;
                }
            }
            if(max < x[i]) max = x[i];
        }
        printf(%d
, max);
    }
    return 0;
}