Tamflexの貯蔵庫

やる気のない備忘録

aoj 0033

玉 | Aizu Online Judge

深さ優先探索で全探索する方法と貪欲的にやる方法がある. 後者のほうが計算量が少なそうだけど, 練習のためdfsでもやる.

貪欲的

int a[10];

bool solve()
{
  int s = 0, t = 0;
  REP(i,10) cin >> a[i];
  REP(i,10)
  {
    if(a[i] > s) s = a[i];
    else if(a[i] > t) t = a[i];
    else return false;
  }
  return true;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  REP(v,n) cout << (solve()?"YES":"NO") << "\n"; 
  return 0;
}

dfs

int a[10];

bool dfs(int l,int r, int num)
{
  if(num == 10) return true;
  bool ans = false;
  if(a[num] > l) ans = dfs(a[num],r,num+1);
  else if(a[num] > r) ans = dfs(l,a[num],num+1);
  return ans;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  REP(v,n)
  {
    REP(i,10) cin >> a[i];
    cout << (dfs(0,0,0)?"YES":"NO") << "\n";
  }
  return 0;
}