백준15826 Namje Adventure

작성일 | In

문제 링크

  • http://icpc.me/15826

사용 알고리즘

  • 플로이드 와샬
  • 비트마스크
  • 행렬 거듭 제곱

시간복잡도

  • {L \choose N} \log (D-N)

풀이

현재 줄의 상태를 L개의 비트로 표현할 수 있습니다.
현재 상태 now에서 맨 위에 있는 사람이 이동해 상태를 nxt로 바꿀 때 소모하는 에너지를 W라고 할 때, now에서 nxt로 가는 간선 W짜리 간선을 만들어줍시다.

깊이가 1인 곳부터 N인 곳까지 사람이 깊이가 D-N-1부터 D인 곳으로 이동하는 것은, (맨 위 N개의 칸에 사람이 있는 상태)에서 출발해 간선 D-N개를 거쳐 다시 (맨 위 N개의 칸에 사람이 있는 상태)인 상태로 돌아오는 것이라고 생각할 수 있습니다.

인접행렬의 (D-N)제곱을 구하면, 간선을 D-N개 거쳐서 가는 최소 비용을 구할 수 있습니다. 단, 이때 행렬곱 연산은 Floyd-Warshall로 정의합니다.

$L \leq 12$라서 정점이 $2^{12}$개라고 생각할 수 있지만, 실제로 가능한 상태는 ${L \choose N}$가지 밖에 없습니다. 좌표 압축을 잘 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct Matrix{
    int n;
    ll v[333][333];
    void init(int _n){
        n = _n; memset(v, 0x3f, sizeof v);
    }
};

Matrix operator * (const Matrix &a, const Matrix &b){
    int n = a.n; Matrix c; c.init(n);
    for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) {
        c.v[i][j] = min(c.v[i][j], a.v[i][k] + b.v[k][j]);
    }
    return c;
}

ll n, d, l, x[22];
ll cst[1<<12][1<<12];

Matrix pw(Matrix a, ll b){
    Matrix ret = a; b--;
    while(b){
        if(b & 1) ret = ret * a;
        b >>= 1; a = a * a;
    }
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> l; for(int i=1; i<=l; i++) cin >> x[i];

    vector<int> comp;
    memset(cst, 0x3f, sizeof cst);
    const int bit = (1 << l);
    for(int i=0; i<bit; i++){
        bool chk[13] = {0};
        vector<int> vec;
        for(int j=0; j<l; j++) if(i & (1 << j)) vec.push_back(j), chk[j] = 1;
        if(vec.size() != n) continue;
        comp.push_back(i);
        if(vec[0] != 0) cst[i][i>>1] = 0;
        for(int j=1; j<=l; j++) if(vec[0]+j <= l && !chk[vec[0]+j]) {
            int t = (i >> 1) | (1 << (vec[0]+j-1));
            cst[i][t] = x[j];
        }
    }

    compress(comp);
    Matrix a; a.init(comp.size());
    for(int i=0; i<comp.size(); i++) for(int j=0; j<comp.size(); j++) a.v[i][j] = cst[comp[i]][comp[j]];
    if(d-n == 0){ cout << 0; return 0; }
    a = pw(a, d-n);
    int st = 0;
    for(int i=0; i<n; i++) st |= (1 << i);
    st = lower_bound(all(comp), st) - comp.begin();
    cout << a.v[st][st];
}