AOJ-2254 : Fastest Route

最短ルート( Fastest Route )

1番から N 番までの N 個のステージがあり，任意の順に攻略することができるゲームがある。ステージを攻略すると、そのクリアー特典として、そのステージの武器が手に入る。武器をつかった場合はそのステージの攻略時間が変化する。全てのステージをクリアーした場合の最短攻略時間を求めよ。

問題の内容的になんとなく動的計画法というのはわかったが、クリアーした順番や、アイテムが使える場合などの判断をどうすればいいか困ったが、bitDP(ビットDP)という手法を用いる事でわかりやすくなった。

dp[ ステージのクリアー状況のビット表記 ] = その状態での最短攻略時間

というDPデーブルを用意し、あとはそのビットの状態を使って、その時点での攻略時間を求めていく

ビットの扱い方は以下を参考にして下さい。

N桁のビットを用意する : bit = 1 << N
ビット表記の i 桁目が立っているか確認 :  ( bit & ( 1<<i ) ) != 0
現在の状態から、i 桁目のビットを１にする :   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;
}