Aizu Online Judge 0146 Lupin The 4th

■0146 Lupin The 4th

動的計画法による解法．

dp[訪れた蔵の集合][現在訪れている蔵]=その状態までの最小時間
とすると，
dp[0][i]=0
dp[k|(1<<i)][i]=min^j{dp[k][j]+|d[i]-d[j]|/(2000/(70+ws[k]))}
となる．
d[i]：城から蔵iの距離
ws[k]：kの蔵全ての千両箱の総重量
計算量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 n;  
17.  int[] name, d, w;  
18.   
19.  void run(){  
20.   n=sc.nextInt();  
21.   name=new int[n];  
22.   d=new int[n];  
23.   w=new int[n];  
24.   for(int i=0; i<n; i++){  
25.    name[i]=sc.nextInt();  
26.    d[i]=sc.nextInt();  
27.    w[i]=sc.nextInt();  
28.   }  
29.   solve();  
30.  }  
31.   
32.  void solve(){  
33.   double[][] dp=new double[1<<n][n];  
34.   int[][] p=new int[1<<n][n];  
35.   int[] ws=new int[1<<n];  
36.   
37.   for(int k=0; k<1<<n; k++){  
38.    for(int i=0; i<n; i++){  
39.     ws[k|(1<<i)]=ws[k]+20*w[i];  
40.    }  
41.   }  
42.   
43.   for(int k=1; k<1<<n; k++){  
44.    Arrays.fill(dp[k], INF);  
45.   }  
46.   
47.   for(int k=0; k<1<<n; k++){  
48.    for(int j=0; j<n; j++){  
49.     for(int i=0; i<n; i++){  
50.      if((k>>i&1)==0){  
51.       double t=dp[k][j]+Math.abs(d[i]-d[j])/2000.0*(70+ws[k]);  
52.       if(t+EPS<dp[k|(1<<i)][i]){  
53.        dp[k|(1<<i)][i]=t;  
54.        p[k|(1<<i)][i]=j;  
55.       }  
56.      }  
57.     }  
58.    }  
59.   }  
60.   
61.   int m=0;  
62.   for(int i=0; i<n; i++){  
63.    if(dp[(1<<n)-1][i]+EPS<dp[(1<<n)-1][m]){  
64.     m=i;  
65.    }  
66.   }  
67.   
68.   LinkedList<Integer> path=new LinkedList<Integer>();  
69.   for(int i=m, sup=(1<<n)-1; sup!=0;){  
70.    path.addFirst(i);  
71.    int j=p[sup][i];  
72.    sup&=~(1<<i);  
73.    i=j;  
74.   }  
75.   
76.   for(int i=0; i<path.size(); i++){  
77.    print(name[path.get(i)]+(i==path.size()-1?"\n":" "));  
78.   }  
79.  }  
80.   
81.  void debug(Object... os){  
82.   System.err.println(Arrays.deepToString(os));  
83.  }  
84.   
85.  void print(String s){  
86.   System.out.print(s);  
87.  }  
88.   
89.  void println(String s){  
90.   System.out.println(s);  
91.  }  
92.   
93.  public static void main(String[] args){  
94.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
95.   new Main().run();  
96.  }  
97. }  

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 n;
 int[] name, d, w;

 void run(){
  n=sc.nextInt();
  name=new int[n];
  d=new int[n];
  w=new int[n];
  for(int i=0; i<n; i++){
   name[i]=sc.nextInt();
   d[i]=sc.nextInt();
   w[i]=sc.nextInt();
  }
  solve();
 }

 void solve(){
  double[][] dp=new double[1<<n][n];
  int[][] p=new int[1<<n][n];
  int[] ws=new int[1<<n];

  for(int k=0; k<1<<n; k++){
   for(int i=0; i<n; i++){
    ws[k|(1<<i)]=ws[k]+20*w[i];
   }
  }

  for(int k=1; k<1<<n; k++){
   Arrays.fill(dp[k], INF);
  }

  for(int k=0; k<1<<n; k++){
   for(int j=0; j<n; j++){
    for(int i=0; i<n; i++){
     if((k>>i&1)==0){
      double t=dp[k][j]+Math.abs(d[i]-d[j])/2000.0*(70+ws[k]);
      if(t+EPS<dp[k|(1<<i)][i]){
       dp[k|(1<<i)][i]=t;
       p[k|(1<<i)][i]=j;
      }
     }
    }
   }
  }

  int m=0;
  for(int i=0; i<n; i++){
   if(dp[(1<<n)-1][i]+EPS<dp[(1<<n)-1][m]){
    m=i;
   }
  }

  LinkedList<Integer> path=new LinkedList<Integer>();
  for(int i=m, sup=(1<<n)-1; sup!=0;){
   path.addFirst(i);
   int j=p[sup][i];
   sup&=~(1<<i);
   i=j;
  }

  for(int i=0; i<path.size(); i++){
   print(name[path.get(i)]+(i==path.size()-1?"\n":" "));
  }
 }

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