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;
}