AOJ-2254 : Fastest Route
1番から N 番までの N 個のステージがあり,任意の順に攻略することができるゲームがある。ステージを攻略すると、そのクリアー特典として、そのステージの武器が手に入る。武器をつかった場合はそのステージの攻略時間が変化する。全てのステージをクリアーした場合の最短攻略時間を求めよ。
問題の内容的になんとなく動的計画法というのはわかったが、クリアーした順番や、アイテムが使える場合などの判断をどうすればいいか困ったが、bitDP(ビットDP)という手法を用いる事でわかりやすくなった。
dp[ ステージのクリアー状況のビット表記 ] = その状態での最短攻略時間
というDPデーブルを用意し、あとはそのビットの状態を使って、その時点での攻略時間を求めていく
ビットの扱い方は以下を参考にして下さい。
N桁のビットを用意する : bit = 1 << N ビット表記の i 桁目が立っているか確認 : ( bit & ( 1<<i ) ) != 0 現在の状態から、i 桁目のビットを1にする : bit = ( bit | ( 1<<i ) )
あとは、ステージのクリアー状態をビットで管理して計算を進めていく。
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254 #include<iostream> #include<map> #include<vector> #include<algorithm> #include<cmath> #include<climits> #include<ctime> #include<cstring> #include<numeric> #define ALL(v) (v).begin(),(v).end() #define REP(i,p,n) for(int i=p;i<(int)(n);++i) #define rep(i,n) REP(i,0,n) #define dump(a) (cerr << #a << "=" << (a) << endl) #define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl; using namespace std; const int INF = INT_MAX; int main() { int N; while(cin >> N && N) { vector< vector<int> > stage( N, vector<int>(N+1,0) ); rep(i,N){ rep(j,N+1){ cin >> stage[i][j]; } } vector<int> dp(1<<N, INF); dp[0] = 0; REP( bit, 0, (1<<N) ) { REP( i, 0, N ) { if( (bit & (1<<i)) != 0 ){ continue; } //既にクリアーされている int cost = stage[i][0]; REP( j, 0, N ) { if( (bit & (1<<j)) == 0 ){ continue; } //この装備は開放されていない cost = min(stage[i][j+1], cost); } int now = (bit | (1 << i));//クリアーした状態にする dp[now] = min(dp[now], dp[bit]+cost); } } cout << dp[(1<<N)-1] << endl; } return 0; }