AOJ-0033 : Ball
問題概要
10個のボールがあり、番号がついている。順序を保ったままボールをふたつの集合に分けるとき、どちらも番号が昇順になるようにできるか判定する問題。
解法
10個しかないので全探索。ボールの数が増えてもDPで解ける。
acceptされたコード
import std.stdio, std.conv, std.algorithm, std.array, std.string; void main(){ int n = to!int(readln.chomp); foreach(_; 0..n){ auto ns = array(map!(to!int)(readln.chomp.split)); writeln(solve(ns) ? "YES" : "NO"); } } bool solve(int[] ns){ foreach(bit; 0..1<<ns.length){ int[2] prev; bool ok = true; foreach(i; 0..ns.length){ if(prev[(bit>>i)&1] < ns[i]){ prev[(bit>>i)&1] = ns[i]; } else{ ok = false; break; } } if(ok){ return true; } } return false; }