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