AOJ 1307 ICPC Asia resional 2010 Problem C: Towns along a Highway

問題

数直線状にn個の点が並んでいる。
一番左側の点のx座標は0である。
各二点間の距離を表す行列（の上半分）が、要素だけを大きい順に並べた形で与えられる。

このときもとの行列を復元せよ。

制約条件

n≦18
d[i]≦400

方針

枝刈り探索。
まず最初に一番遠くの点が自明にわかる。

そこから探索していく。
要素を大きい順に取り出して、左端の点からみて右に置くか左に置くかの二通りがあるので再帰して探索する。

ソースコード

int n,d[200],cnt[401];
set<vi> ans; vi tmp;
void rec(int c,int right){
	//cerr<<c<<" "<<right<<endl;
	//rep(i,tmp[0]+1)if(cnt[i])rep(j,cnt[i])cerr<<i<<" "; cerr<<endl;
	if(c==n){
		vi d,e=tmp; sort(all(e));
		rep(i,n-1)d.pb(e[i+1]-e[i]);
		if(!ans.count(d))ans.insert(d);
		return;
	}
	int mx=right;
	for(;mx>=0&&cnt[mx]==0;mx--);
	if(mx<0)return;
	
	rep(it,2){
		tmp.pb(mx);
		bool ok=1;
		rep(i,c)if(--cnt[abs(tmp[i]-mx)]<0)ok=0;
		if(ok)rec(c+1,it?tmp[0]-mx:mx);
		rep(i,c)cnt[abs(tmp[i]-mx)]++;
		tmp.erase(tmp.begin()+c);
		
		if(mx==tmp[0]-mx)break;
		mx=tmp[0]-mx;
	}
}

int main()
{
	while(cin>>n,n){
		ans.clear();
		rep(i,401)cnt[i]=0;
		rep(i,n*(n-1)/2)cin>>d[i],cnt[d[i]]++;
		
		int mx=*max_element(d,d+n*(n-1)/2);
		tmp.clear(); tmp.pb(mx); tmp.pb(0); cnt[mx]--;
		rec(2,mx);
		fr(i,ans)rep(j,n-1)cout<<(*i)[j]<<(j==n-2?"\n":" ");
		cout<<"-----"<<endl;
	}
	return 0;
}