Aizu Online Judge 0120 Patisserie

■0120 Patisserie

r₁のロールケーキにr₂のロールケーキを並べると，
長さが2√(r₁r₂)-r₁+r₂だけ増える．
dp[k][S]=右端がロールケーキk，集合Sのロールケーキを既に並べたとしたときの最小の長さ
としてDP．計算量はO(2ⁿn²)．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int len, n;  
17.  int[] a;  
18.   
19.  void run(){  
20.   for(;sc.hasNext();){  
21.    String[] ss=sc.nextLine().split(" ");  
22.    len=Integer.parseInt(ss[0]);  
23.    n=ss.length-1;  
24.    a=new int[n];  
25.    for(int i=0; i<n; i++){  
26.     a[i]=Integer.parseInt(ss[i+1]);  
27.    }  
28.    solve();  
29.   }  
30.  }  
31.   
32.  void solve(){  
33.   double[][] dp=new double[1<<n][n];  
34.   for(int j=0; j<1<<n; j++){  
35.    fill(dp[j], INF);  
36.   }  
37.   for(int i=0; i<n; i++){  
38.    dp[1<<i][i]=2*a[i];  
39.   }  
40.   for(int s=1; s<1<<n; s++){  
41.    for(int j=0; j<n; j++){  
42.     if((s>>j&1)==0){  
43.      continue;  
44.     }  
45.     for(int i=0; i<n; i++){  
46.      if((s>>i&1)==0){  
47.       dp[s|1<<i][i]=min(dp[s|1<<i][i],  
48.         dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);  
49.      }  
50.     }  
51.    }  
52.   }  
53.   double min=INF;  
54.   for(int i=0; i<n; i++){  
55.    min=min(min, dp[(1<<n)-1][i]);  
56.   }  
57.   println(min<len+EPS?"OK":"NA");  
58.  }  
59.   
60.  void debug(Object... os){  
61.   System.err.println(Arrays.deepToString(os));  
62.  }  
63.   
64.  void print(String s){  
65.   System.out.print(s);  
66.  }  
67.   
68.  void println(String s){  
69.   System.out.println(s);  
70.  }  
71.   
72.  public static void main(String[] args){  
73.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
74.   new Main().run();  
75.  }  
76. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int len, n;
 int[] a;

 void run(){
  for(;sc.hasNext();){
   String[] ss=sc.nextLine().split(" ");
   len=Integer.parseInt(ss[0]);
   n=ss.length-1;
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=Integer.parseInt(ss[i+1]);
   }
   solve();
  }
 }

 void solve(){
  double[][] dp=new double[1<<n][n];
  for(int j=0; j<1<<n; j++){
   fill(dp[j], INF);
  }
  for(int i=0; i<n; i++){
   dp[1<<i][i]=2*a[i];
  }
  for(int s=1; s<1<<n; s++){
   for(int j=0; j<n; j++){
    if((s>>j&1)==0){
     continue;
    }
    for(int i=0; i<n; i++){
     if((s>>i&1)==0){
      dp[s|1<<i][i]=min(dp[s|1<<i][i],
        dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);
     }
    }
   }
  }
  double min=INF;
  for(int i=0; i<n; i++){
   min=min(min, dp[(1<<n)-1][i]);
  }
  println(min<len+EPS?"OK":"NA");
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}