AOJ0120

Patisserie

■問題
幾つかの円を任意の順番で並べたとき必要な幅の最小が箱の幅より小さいかどうかを求める。

■解法
dp[直前に度の円を使ったか][使った円の集合]で横幅を求めて、それがはこの大きさより小さいかを判定する。
2円の中点を繋ぐ線分はr1+r2、2円の中点の高さの差はr1-r2でも止まるので三平方の定理で2円の中点の間の横幅を求めることができるので頑張る。
入力が非常に悪質なのでfgets()とかsscanf()とか使って頑張る。
入力が一番難しい。

■ソース

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int n,l;
char len[1111];
int r[22];
 
double dp[22][5555];
 
double sq(int a){return a*a;}
 
double solve(int af,int used){
  if(dp[af][used] >= 0) return dp[af][used];
 
  if(used == (1<<n)-1) return 0;
 
  double ret = 4444;
  for(int i = 0; i < n; i++){
    if(af == n) r[af] = r[i];
    if( (used & (1<<i)) == 0 ){
      ret = min(ret, solve(i, used | (1<<i)) + sqrt(sq(r[i] + r[af]) - sq(r[i] - r[af])) - r[af] + r[i]);
    }
  }
  return dp[af][used] = ret;
}
 
 
int main(void)
{
  while( fgets(len, sizeof(len), stdin) != NULL ){
    n=0;
 
    vector<char*> d;
    for(int i = 0; len[i] != '\0'; i++){
      if(len[i] == ' '){
    d.push_back(len+i+1);
    n++;
      }
    }
    sscanf(len,"%d",&l);
    for(int i = 0; i < n; i++){
      sscanf(d[i],"%d",&r[i]);
    }
 
    for(int i = 0; i <= n; i++){
      for(int j = 0; j < 5555; j++){
    dp[i][j] = -1;
      }
    }
    double ret = solve(n,0);
    if(ret > l) puts("NA");
    else puts("OK"); 
  }
}