POJ 3298 Antimonotonicity (思维)-白红宇

POJ 3298 Antimonotonicity (思维)

阅读量：4562 次

发布时间：2019-06-08

本文共 897 字，大约阅读时间需要 2 分钟。

题目链接：

找一个最长不要求连续的子序列，如a1 > a3 < a6 > a7 ...

举个例子模拟一下差不多明白了，a[i - 1]与a[i]有依赖关系。

1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               13 using namespace std;14 typedef long long LL;15 typedef pair 
                
                  P;16 const int N = 1e5 + 5;17 int a[N];18 19 int main()20 {21 int t, n;22 scanf("%d", &t);23 while(t--) {24 scanf("%d", &n);25 for(int i = 1; i <= n; ++i) {26 scanf("%d", a + i);27 }28 int Max = 1, num = a[1];29 for(int i = 2; i <= n; ++i) {30 if(Max % 2 && a[i] < num) {31 Max++;32 } else if(Max % 2 == 0 && a[i] > num) {33 Max++;34 }35 num = a[i];36 }37 printf("%d\n", Max);38 }39 return 0;40 }