TopCoder SRM 354 Div1 Medium RemissiveSwaps

問題

数字に対して次の操作が好きなだけ出来る。
0でない桁を二つ選び、それぞれから1を引いたあと、それぞれを交換する。

Nが与えられたとき、操作を0回以上して得られる数のうち、最大のものを求めよ。

制約条件

N≦1000000

方針

全探索するだけ。

ソースコード

setを使ったらギリギリになってしまった。
配列でやると余裕。

int n,d[7],ans;
set<int> s;
void rec(){
	int m=0;
	rep(i,n)m*=10,m+=d[i];
	if(s.count(m))return;
	ans=max(ans,m);
	s.insert(m);
	
	rep(i,n)rep(j,i)if(d[i]&&d[j]){
		swap(d[i],d[j]);
		d[i]--; d[j]--;
		rec();
		swap(d[i],d[j]);
		d[i]++; d[j]++;
	}
}

class RemissiveSwaps {
	public:
	int findMaximum(int N) 
	{
		ans=N;
		for(n=0;N;N/=10)d[n++]=N%10;
		reverse(d,d+n);
		if(n==0)d[n++]=0;
		s.clear();
		rec();
		return ans;
	}
};