AOJ 0120 - Patisserie

すこしbitDP書けるようになった．いままでループで，はじめてメモ化再帰書いた．
こっちのほうがいいかも．

Sは今まで使ったケーキ，vはさっき使ったケーキ
dp[S][v]は残りのケーキでできる最小幅．
全ケーキの幅になるよう最初に使ったケーキの半径と最後に使ったケーキの半径を足している．

#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>

const int MAX_N = 12, INF = 1 << 16;
double dp[1 << MAX_N][MAX_N], rs[MAX_N];
int n;

inline double square(double d){
	return d * d;
}

double rec(int S, int v){
	if(dp[S][v] >= 0){
		return dp[S][v];
	}

	if(S == (1 << n) - 1){
		return rs[v];
	}

	double res = INF;
	for(int u=0;u<n;u++){
		if(!(S >> u & 1)){//未使用
			res = std::min(res, rec(S | (1 << u), u) + sqrt(square(rs[v]+rs[u]) - square(rs[v]-rs[u])));
		}
	}

	return dp[S][v] = res;
}

int main(){
	double box_l, min_l;
	while(std::cin >> box_l){
		if(std::cin.eof()){
			return 0;
		}

		min_l = INF;
		n = 0;

		std::string str;
		std::getline(std::cin, str);

		std::stringstream ss(str);
		while(!ss.eof()){
			int _i;
			ss >> _i;
			rs[n++] = _i;
			ss.ignore();
		}

		for(int i=0;i<n;i++){//iを始めにした最小幅をもとめる
			for(int j=0;j<(1<<MAX_N);j++){
				for(int k=0;k<MAX_N;k++){
					dp[j][k] = -1;
				}
			}

			min_l = std::min(min_l, rec(1 << i, i) + rs[i]);
		}

		if(min_l <= box_l){
			puts("OK");
		}else{
			puts("NA");
		}
	}
}