0120-Patisserie

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0120&lang=jp
最初はn!のすべての並び方を試していたが、時間内に間に合わなかった。
そしてグラフに直してみたら循環セールスマン問題ということに気づいて、
プロコン本を参考にしつつAccepted
考え方
すべての経路を通り最初に戻ってくるということで、循環セールスマン問題に落としこめる。

実装(C++/インクルード省略)

const int MAX_N=13;
const int INF=999999;
double k[11][11];//半径aのケーキの隣に半径bのケーキを置いたとき、半径bはどのくらいの先にあるか
double d[MAX_N][MAX_N];
double dp[1<<MAX_N][MAX_N];
int n,t,a[MAX_N],w;
void maked(){//循環経路の接続を考える
	for(int i=0;i<n+1;i++){
		for(int j=0;j<n+1;j++){
			d[i][j]=INF;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			d[i][j]=k[a[i]][a[j]];
		}
	}
	for(int i=0;i<n;i++){
		d[n][i]=a[i];
		d[i][n]=a[i];
	}
	n=n+1;
}
void calc(){
	int i,j;
	for(i=3;i<11;i++){
		for(j=3;j<11;j++){
			k[i][j]=sqrt((i+j)*(i+j)-(i-j)*(i-j));
		}
	}
}
double rec(int bit,int s){
	if(dp[bit][s]>=0) return dp[bit][s];
	double res=INF;
	if(bit==(1<<n)-1&&s==0)return dp[bit][s]=0;
	for(int i=0;i<n;i++){
		if(!(bit>> i &1)){
			res=min(res,rec(bit | 1<<i,i)+d[s][i]);
		}
	}
	return dp[bit][s]=res;
}
void clearDP(){
	for(int i=0;i<(1<<MAX_N);i++)
		for(int j=0;j<MAX_N;j++)
			dp[i][j]=-1;
}
int main() {
	calc();
	while(1){
		for(int i=0;i<13;i++)a[i]=0;
		if(scanf("%d ",&w)==EOF)return 0;
		n=0;
		while(1){
			t=getchar();
			if(t==' ') n++;
			else if(t=='\n'){n++;break;}
			else{
				a[n]=a[n]*10+t-'0';
			}
		}
		clearDP();
		maked();
		if((double)w>=rec(0,0))puts("OK");else puts("NA");
	}
	return 0;
}