UVa 11240 : Antimonotonicity

問題リンク : http://uva.onlinejudge.org/external/112/11240.html

問題概要:
n個の要素からなる配列が与えられる
この部分列のなかで以下の条件を満たすもののうち最長のものの長さを求めよ
A > B < C > D < ....

解法 :
貪欲に決めていく（考え方的にはDP？）
n個の配列を最初の要素から順にみていく
答えとなる配列（以下array）を用意する
もしarrayが空なら今みている要素を入れる
空でないのなら、
arrayのサイズが偶数の時（次に入れる値との関係が < となる時）
もし、arrayの一番最後の要素よりも今見ている配列の要素の方が小さいなら
arrayの一番最後の要素に今見ている値を代入する
次に入れる値との関係が < となるのでここでは値が最も小さいものを入れておいたほうが良いから
そうでない場合、arrayに今見ている値をpushする

arrayのサイズが奇数の時（次に入れる値との関係が > となる場合）
もし、arrayの一番最後の要素よりも今みている配列の要素の方が大きいなら
arrayの一番最後の要素に今見ている値を代入する
これも < の場合と同じ理由
そうでない場合、arrayに今見ている値をpushする

これらは、今みている値を使うか使わないかを全てためしている
arrayの最後の値に代入する場合は、１つ前の値は使わないということで
arrayに値をpushする場合は、その値を（とりあえず）使う場合となる

コード：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<climits>
#include<vector>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)

using namespace std;

int main(){
  int T;
  cin >> T;
  while(T--){
    int n;
    cin >> n;
    int array[n];
    rep(i,n)cin >> array[i];

    vector<int> seq;

    rep(i,n){
      if(seq.empty()){
	seq.push_back(array[i]);
	continue;
      }
      int len = seq.size();
      if(len & 1){
	if(seq[len-1] < array[i]){
	  seq[len-1] = array[i];
	}
	else if(seq[len-1] > array[i]){
	  seq.push_back(array[i]);
	}
      }
      else{
	if(seq[len-1] > array[i]){
	  seq[len-1] = array[i];
	}
	else if(seq[len-1] < array[i]){
	  seq.push_back(array[i]);
	}
      }
    }
    cout << seq.size() << endl;
  }
  return 0;
}