Japan Alumni Group Summer Camp 2015 Day 2 D - 真っ暗な部屋
解法
見た目からわかるように bitDP で解きます。
dp[state] = (今暗い部屋のうち state で表される部屋にいる可能性がある場合の, 最小移動距離) とします。
すると, 各部屋から i 番目の部屋に移った時の次の状態 nstate がわかります。その nstate について再び最小移動距離を求める, ということを繰り返すことによって答えを求めることが出来ます。
下の実装はかなり雑で, 1 秒くらいかかってしまいましたが, inD を求めるところを O(M) ではなく O(1) でできるのでそれで 16 倍です。
const int MAXM = 16; const int MAXN = 101; const int INF = 1e9; int N, M, K; int D[MAXM]; int v[MAXN][MAXN]; int dp[1<<MAXM]; int dfs(int state) { if (state == 0) return 0; int& ret = dp[state]; if (ret >= 0) return ret; ret = INF; for (int i = 0; i < K; i++) { int nstate = 0; for (int j = 0; j < M; j++) { if ((state>>j)&1) { int next = v[D[j]][i]; int inD = -1; for (int k = 0; k < M; k++) if (D[k] == next) { inD = k; break; } if (inD != -1) nstate |= (1<<inD); } } if (state == nstate) continue; ret = min(ret, 1+dfs(nstate)); } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> M >> K; for (int i = 0; i < M; i++) { cin >> D[i]; D[i]--; } for (int i = 0; i < N; i++) for (int j = 0; j < K; j++) { cin >> v[i][j]; v[i][j]--; } memset(dp, -1, sizeof(dp)); cout << dfs((1<<M)-1) << endl; return 0; }