Problem 0146 : Lupin The 4th

Problem 0146 : Lupin The 4th
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0146

• 問題概要

あちこち回って荷物を回収するが、荷物をもてばもつほど、うごきが遅くなる。

• 解法

DP.　ビットで荷物の状態を表しループを回す。
dp[今どこか][ビットでどの荷物を拾ったか];

• ソース

#include<iostream>
#include<algorithm>
#include<vector>

#define INF 1e+100
#define vint vector<int>

using namespace std;

main(){
  int n; 
  cin >> n;

  int MAX = (1<<n), ID[n], d[n], box[n];
  
  for(int i=0; i<n; i++){
    cin >> ID[i] >> d[i] >> box[i];
  }

  double dp[n][MAX];
  vint path[n][MAX];

  int w[MAX];

  for(int i=0; i<MAX; i++){
    int sum=0, cnt=0;
    for(int j=1; j<MAX; j=(j<<1), cnt++){
      if((i&j) != 0){
	sum += box[cnt];
      }
    }
    w[i] = sum * 20;
  }

  fill(&dp[0][0], &dp[n-1][MAX], INF);
  
  for(int i=0; i<n; i++){
    dp[i][1<<i] = 0;
    path[i][1<<i].push_back(i);
  }


  for(int i=0; i<MAX; i++){
    double v = 2000.0/(double)(70 + w[i]);
    for(int j=0; j<n; j++){
      int now = (1 << j);
      if( (i&now) == 0)continue;
      for(int k=0; k<n; k++){
	int next = (1 << k);
	if( (i&next) > 0)continue;
	double cost = (double)(abs(d[j] - d[k]))/v;
	if(dp[k][i|next] > dp[j][i] + cost){
	  dp[k][i|next] = dp[j][i] + cost;
	  path[k][i|next] = path[j][i];
	  path[k][i|next].push_back(k);
	}
      }
    }
  }

  double min = INF;
  vint ans;
  
  for(int i=0; i<n; i++){
    if(min > dp[i][MAX-1]){
      min = dp[i][MAX-1];
      ans = path[i][MAX-1];
    }
  }   
  for(int i=0; i<ans.size(); i++){
    if(i != 0){
      cout << ' ';
    }
    cout << ID[ans[i]];
  }
  cout << endl;
}

楽しかった。DPは楽しい。