土下座しながら探索中

主に競技プログラミング

 AOJ 0120 : Patisserie

問題リンク:Patisserie | Aizu Online Judge

問題概要:
箱の長さとn個のケーキの半径が与えられる(1 <= n <= 12)
与えられた箱のにすべてのケーキを収めることができるか?
大きなケーキの間に小さいケーキがはまり込むことはない

解法:
ビットDP
ケーキの数が最大12なのでギリギリ全部試してもいけるか?と思ったがいけなかった

dp[i][j] (iは既に置いたケーキをビットで表したもの ビットが立って入ればすでに置いたものとした
jは一番左に置いてあるケーキ) という配列を用意した

dp[i][j] := 状態iの一番左のケーキがjの時に必要な箱の最小値 とした
ただし、iで立っているビットの数がケーキの数と等しい時以外は最後の円の半径を足していない

for i 0..(1<<ケーキの数)-1
  for j 0..ケーキの数
    for k 0..ケーキの数
      if dp[i][k] == inf 
        continue
      else
        dp[i|(1<<j)][j] = min(dp[i|(1<<j)][j],
                              dp[i][k] + distance(k,j)

distance(k,j)は円kと円jの距離
上の擬似コードにi==0なら半径をいれるだけ
i|(1<

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<complex>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<sstream>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29) 
#define EPS (1e-10)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)

using namespace std;

class Point
{
  public:
  double x,y;

  Point(double x = -1,double y = -1): x(x),y(y){}

  Point operator + (Point p ){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}//※イケメンに限る

  bool operator < (const Point& p) const
  {
    return x != p.x?x<p.x:y<p.y;
  }

  bool operator == (const Point& p)const
  {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }

//必要に応じて
double norm()
{
return x*x+y*y;
}

};

struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(-1,-1),Point p2 = Point(-1,-1)):p1(p1),p2(p2){}
};
typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;


double dot(Point a,Point b)
{
  return a.x*b.x + a.y*b.y;
}
double cross(Point a,Point b)
{
  return a.x*b.y - a.y*b.x;
}

double norm(Point a)
{
  return a.x*a.x+a.y*a.y;
}

bool pequals(Point a,Point b)
{
  return equals(a.x,b.x) && equals(a.y,b.y);
}

//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad)
{
  return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y);
}

// 度をラジアンに変換
double toRad(double agl)
{
  return agl*M_PI/180.0;
}

double angle(Point a,Point b,Point c)
{
  double ux = b.x - a.x, uy = b.y - a.y;
  double vx = c.x - a.x, vy = c.y - a.y;
  return acos((ux*vx + uy*vy)/sqrt((ux*ux + uy*uy) * (vx*vx + vy*vy)));
}  

double args(Point p){
  return atan2(p.y,p.x);
}

double L;

void split(string s,vector<double> &vec)
{
  stringstream ss;
  ss << s;
  for(int i=0;!(ss >> s).fail();i++)
    {
      if(i == 0)L = (atoi)(s.c_str());
      else
	{
	  vec.push_back((atoi)(s.c_str()));
	}
    }

}

int n;
double dp[(1<<12)][12];

double getDistance(double r1,double r2)
{
  return sqrt(pow(r1+r2,2)-pow(r1-r2,2));
}

int main()
{

  string line;
  while(getline(cin,line))
    {
      vector<double> vec;
      split(line,vec);
      n = vec.size();
      rep(i,(1<<n))rep(j,n)dp[i][j] = inf;

      rep(i,(1<<n))//これまでに置いた円の状態
	{
	  rep(j,n)//次にどの円を一番左に追加するのか
	    {
	      rep(k,n)//今一番左にある円はどれか?
		{
		  if(i == 0)//まだ1つも円を置いていないなら半径のみをいれる
		    {
		      dp[i|(1<<j)][j] = min(dp[i|(1<<j)][j],vec[j]); 
		      continue;
		    }
		  
		  if(dp[i][k] == inf)continue;
		  int next = i|(1<<j);

		  if(__builtin_popcount(next) == n)//最後の円なので円と円の距離+最後にいれる円の半径
		    {
		      dp[next][j] = min(dp[next][j],
					dp[i][k]+getDistance(vec[k],vec[j])+vec[j]);
		    }
		  else
		    {
		      dp[next][j] = min(dp[next][j],
					dp[i][k]+getDistance(vec[k],vec[j]));
		    }
		}
	    }
	}

      double ans = inf;
      rep(i,n)ans = min(ans,dp[(1<<n)-1][i]);
      if(equals(ans,L) || (!equals(ans,L) && ans < L))cout << "OK" << endl;
      else        cout << "NA" << endl;
    }
  return 0;
}