TopCoder SRM 358 Div1 Easy BrokenButtons

問題

機械に数字を入力したい。
0〜9のキーおよび、+と-のボタンがある。

1. と-のボタンは表示されている数字を+1または-1する。

0〜9のキーのうち、broken[]の要素のものは壊れてしまっていて使えない。
pageの数字を入力するのに必要なボタンの押下回数の最小値を求めよ。

ただし、何もキーを押さない状態では、100の数字が表示されている。
また、+,-のボタンは数字のボタンを押し終えてからしか使えないものとする。

制約条件

0≦broken[i]≦9
broken[]の要素数≦10

方針

使えるボタンの中で、元の数字が押せたら押す。
不可能なら、「元の数字よりも大きいもので最小のもの」を作って-する、
または「元の数字よりも小さいもので最大のもの」を作って+する。

一桁ずつ見ていくDPみたいな感じで探索を書けばよい。

ソースコード

bool can[10];
int ans,n,m,d[30],p;
void rec(int pos,int cmp,int cur,int cost){
	if(pos==m){
		ans=min(ans,abs(cur-p)+cost);
		return;
	}
	if(cmp==0){
		rep(i,10)if(can[i]){
			int ncmp=0;
			if(i!=d[pos])ncmp=i<d[pos]?-1:1;
			rec(pos+1,ncmp,cur*10+i,cost+1);
		}
	}
	if(cmp<0)for(int i=9;i>=0;i--)if(can[i]){
		rec(pos+1,cmp,cur*10+i,cost+1);
		break;
	}
	if(cmp>0)rep(i,10)if(can[i]&&(pos>=0||i)){
		rec(pos+1,cmp,cur*10+i,cost+1);
		break;
	}
}
class BrokenButtons {
	public:
	int minPresses(int page, vector <int> broken) 
	{
		rep(i,10)can[i]=1;
		n=broken.size(); ans=abs(page-100);
		rep(i,n)can[broken[i]]=0;
		p=page;
		for(m=0;page;page/=10)d[m++]=page%10;
		reverse(d,d+m);
		if(m==0)m++;
		rec(0,0,0,0); //同じ桁数で出来るだけ近いものを作る
		rec(-1,1,0,0); //1桁多い数字で最小のものを作る
		if(m>1)rec(1,-1,0,0); //1桁少ない数字で最大のものを作る
		return ans;
	}