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²)

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