블로그 옮겼습니다

UVa OJ 1407 - Caves 본문

Algorithm/Problem Solving

UVa OJ 1407 - Caves

sgc109 2017. 6. 29. 11:07
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4153

n개의 노드로 이루어진 트리가 있고 간선에는 기중치가 있다.
q개의 쿼리가 주어진다.
각 쿼리마다 연료의 양 x가 주어진다.
루트노드부터 시작하여(루트 노드는 암시적으로 결정되어있음) 연료 x로 방문할 수 있는 최대 노드의 수를
각 줄에 출력한다.

이 문제는 트리 dp 문제인데 부분문제를 두개 정의해야 한다.

dp1[i][j]
= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 돌아오는 최소비용

dp2[i][j]
= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 안돌아와도 되는 최소비용

dp1은 dp1끼리의 점화식으로 모두 구할 수가 있으며, dp1은 dp2를 계산하기 위해 필요하기 때문에 구한다.
dp2[root] 배열은 root에서 시작하여 다시 안돌아와도 될 때 j개의 노드를 방문하는 데에 필요한 최소 비용을
가지고 있기 때문에 당연하게도 비용이 오름차순으로 정렬되어 있을 것이다. 그러므로 비용이 x보다 작거나 같은
최대 인덱스를 구하면 그게 쿼리의 답이다.

그렇다면 dp1과 dp2는 어떻게 구할까?

우선 현재 i노드에 있다고 해보자. 이럴 때 유용하고 자주 쓰이는 테크닉 중 하나는
앞의 k개의 가지를 합쳐준 결과와 k번째가지를 합쳐주고, 그럼 결과적으로 k+1개의 가지를 합쳐준 결과를
가지고 있게 될텐데 그것과 k+1번째 가지를 합쳐주고.... 를 반복하여 마지막 가지까지 합쳐주면 된다.

dp1을 구할 때는 어차피 몇개를 방문하던 어떤 가지로 내려가던 다시 돌아와야하기 때문에 단순히 그냥 합치면된다.
dp2를 구할 때는 조금 다르다. 2개 이상의 가지로 내려간다면 마지막 가지를 제외 하고는 다시 돌아오며
마지막 가지는 돌아오지 않는다. 그렇기 때문에
1. 지금까지 합친 dp1과 지금 보는 가지의 dp2를 합치는경우와
2. 지금까지 합친 dp2와 지금 보는 가지의 dp1를 합치는경우

이 두가지의 최소값으로 현재 가지를 합친 dp2를 구할 수 있다.
즉 지금까지 합친 dp1 이라는건 앞의 가지들로는 갔다가 돌아왔다는 것이기 때문에
1번 경우는 앞의 가지들로는 갔다 오고 현재 보는 가지는 갔다가 안돌아오는 경우이며
2번 경우는 앞의 가지들중에 하나는 갔다가 안돌아올 것이 정해졌기에 현재 보는 가지는 갔다가 돌아오는 경우로
계산하는 것이다.


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
69
70
71
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int dp1[503][503], dp2[503][503];
int tdp1[503], tdp2[503];
int sz[503];
int n,q;
vector<pair<int,int> > G[503];
int check[503];
int dfs(int here){
    dp1[here][1= dp2[here][1= 0;
    sz[here] = 1;
    if(G[here].size() == 0return sz[here] = 1;
    for(auto p : G[here]) {
        int there = p.first;
        sz[here] += dfs(there);
    }
    int size = 1;
    for(int i = 0 ; i < (int)G[here].size(); i++){
        int there = G[here][i].first;
        int cost = G[here][i].second;
        for(int i = 0 ; i < 503; i++) tdp1[i] = dp1[here][i], tdp2[i] = dp2[here][i];
        for(int k = 1 ; k <= sz[there]; k++){
            tdp1[k] = min(tdp1[k], dp1[there][k-1+ 2 * cost);
            tdp2[k] = min(tdp2[k], dp2[there][k-1+ cost);
            for(int j = 1 ; j <= size; j++){
                tdp1[j+k] = min(tdp1[j+k], dp1[here][j] + dp1[there][k] + 2 * cost);
                tdp2[j+k] = min(tdp2[j+k], dp1[here][j] + dp2[there][k] + cost);
                tdp2[j+k] = min(tdp2[j+k], dp2[here][j] + dp1[there][k] + 2 * cost);
            }
        }
        for(int i = 0 ; i < 503; i++) dp1[here][i] = tdp1[i], dp2[here][i] = tdp2[i];
        size += sz[there];
    }
    
    return sz[here];
}
int main() {
    for(int t = 1; ; t++){
        for(int i = 0 ; i < 503; i++) G[i].clear();
        memset(dp1,0x3c,sizeof(dp1));
        memset(dp2,0x3c,sizeof(dp2));
        memset(check,0,sizeof(check));
        memset(sz,0,sizeof(sz));
        cin >> n;
        if(!n) break;
        for(int i = 0 ; i < n-1; i++){
            int c,p,d;
            cin >> c >> p >> d;
            check[c] = 1;
            G[p].emplace_back(c,d);
        }
        int root = -1;
        for(int i = 0 ; i < n; i++if(!check[i]) root = i;
        dfs(root);
 
        cout << "Case " << t << ":" << endl;
        cin >> q;
        for(int i = 0 ; i < q; i++){
            int x;
            cin >> x;
            int pos = upper_bound(dp2[root]+1, dp2[root]+1+sz[root], x) - dp2[root] - 1;
            cout << pos << endl;
        }
    }
    return 0;
}
cs


Comments