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; }