블로그 옮겼습니다

UVa OJ 12452 - Plants vs. Zombies HD SP 본문

Algorithm/Problem Solving

UVa OJ 12452 - Plants vs. Zombies HD SP

sgc109 2017. 6. 29. 12:00
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3883


노드가 N개인 트리가 주어진다. 트리의 각 노드에 최대 한개의 식물을 놓아 간선들을 보호해야한다.
식물은 세가지가 있다. 

1번 :  $100 이며 인접한 간선 하나 보호가능
2번 : $175 이며 인접한 간선 두개 보호가능
3번 : $500 이며 인접한 모든 간선 보호가능

간선을 모두 보호하기 위해 필요한 최소 비용을 구하는 문제이다.

dp[i][j] : i는 현재 노드, j는 나의 부모를 연결하는 엣지를 부모가 보호해줬는지 여부 true/false 일 때
인접한 간선을 모두 보호하기 위한 최소 비용

이라고 부분문제를 정의해 보자.

그럼 dp[i][0] 은 세가지 케이스 중 최소값이 되는데
1. i의 모든 자식들이 i와 연결하는 엣지를 알아서 보호하면 $100가 필요하며(현재 j가 0이므로 부모와 잇는 간선 보호해야함)
2. 하나의 자식이 알아서 보호하지 않는다면 그 자식과 부모와 잇는 간선, 이렇게 총 두개를 i가 보호해야하므로 $175가 필요하며
3. $500 를 쓴다면 자식들은 모두 부모와 잇는 간선은 신경쓰지않아도 된다. 즉,
첫번째 경우는 모든 자식들 c에 대해 dp[c][0] 의 합 + $100 이고
두번째 경우는 미리 sum이라는 변수에 dp[c][0]의 합을 구해놓고 하나의 노드에 대해서만 -dp[c][0]+dp[c][1] 를
해주면 그 가지는 부모인 i가 커버해준 다는 뜻이므로 여기에 $175를 더하는식으로 모든 자식에 대해 반복하여
답을 갱신하면 된다.
세번째 경우는 모든 자식들 c에 대해 dp[c][1] 의 합 + $500 이다.

이번엔 dp[i][1] 이다. 이것은 네가지 케이스로 나뉜다.
1. i의 모든 자식들이 부모와 잇는 엣지를 알아서 커버한다면 i에는 식물을 놓지않아도 되므로(j가 1이라서) $0 필요
2. 하나의 자식이 알아서 보호하지 않는다면 $100 필요
3. 두개의 자식이 알아서 보호하지 않는다면 $175 필요
4. $500 을 쓴다면 모든 자식들은 부모와의 간선을 신경쓰지 않아도됨
첫번째 경우는 모든 자식 c에 대해 dp[c][0] 의 합이다.
두번째 경우는 모든 자식 c에 대해 dp[c][0] 의 합을 구해놓고 dp[i][0] 에서의 두번째 경우처럼 -dp[c][0]+dp[c][1] 를
모든 자식에 대해 반복하는데 대신 여기에선 i의 부모와의 엣지를 부모가 보호해주므로 $100를 더해서 답을 갱신
세번째 경우가 사실 제일 중요하다. 자식과 연결된 두 엣지를 i가 보호해야 하는데 뭘 선택해야 하는 문제이다.
우선 만약 a자식과 연결된 엣지와 b자식과 연결된 엣지를 i가 보호해 준다면
모든 자식 c에 대해 dp[c][0]의 합을 sum이라고 할 때 sum - dp[a][0] + dp[a][1] - dp[b][0] + dp[b][1] 의 최소값을
찾아야 하는 것이므로 -dp[k][0] + dp[k][1] 가 가장 작은 두 자식 k를 구해야 한다. 간단하게 정렬을 하여
0번째, 1번째 인덱스를 취하는 식으로 하면 구현은 가장 간단하다. 이걸 O(n) 에 하려면
이곳 을 참조하면 된다. 아무튼 이걸 구한뒤 sum과 더한뒤 $175를 더한것을 답과 갱신하면 된다.

네번째 경우는 dp[i][0]의 세번째와 동일하다.

이렇게 하면 dp[root][1] 에 답이 있을 것이다. (root는 부모가없으므로 위의 엣지는 신경쓰지 않아도 되기 때문에

부모가 이미 보호해주는 것과 같다고 볼 수가 있다.)


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
72
73
74
75
76
77
78
#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 T,N;
vector<int> G[10003];
int dp[10003][2];
void dfs(int here, int dad){
    if(G[here].size() == 1 && G[here][0== dad) {
        dp[here][0= 100;
        dp[here][1= 0;
        return;
    }
    int allSel = 0;
    int noSel = 0;
    for(int there : G[here]){
        if(there == dad) continue;
        dfs(there, here);
        allSel += dp[there][0];
        noSel += dp[there][1];
    }
    
    // 부모가 나와 잇는 엣지 보호 안해준 경우
    int& dp0 = dp[here][0];
    dp0 = inf;
    // case 1
    dp0 = min(dp0, allSel + 100); 
    
    // case 2
    for(int there : G[here]) {
        if(there == dad) continue;
        dp0 = min(dp0, allSel - dp[there][0+ dp[there][1+ 175);
    }
    // case 3
    dp0 = min(dp0, noSel + 500);
 
    // 부모가 나와 잇는 엣지 보호해준 경우
    int& dp1 = dp[here][1];
    dp1 = inf;
    // case 1
    dp1 = min(dp1, allSel);
 
    // case 2
    for(int there : G[here]) {
        if(there == dad) continue;
        dp1 = min(dp1, allSel - dp[there][0+ dp[there][1+ 100);
    }
 
    // case 3
    int minn = inf, ans = inf;
    for(int there : G[here]) {
        if(there == dad) continue;
        ans = min(ans, minn - dp[there][0+ dp[there][1]);
        minn = min(minn, -dp[there][0+ dp[there][1]);
    }
    dp1 = min(dp1, allSel + ans + 175);
 
    // case 4
    dp1 = min(dp1, noSel + 500);
}
int main() {
    cin >> T;
    while(T--){
        for(int i = 0 ; i < 10003; i++) G[i].clear();
        cin >> N;
        for(int i = 0 ; i < N-1; i++) {
            int u,v;
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(0,-1);
        cout << '$' << dp[0][1<< endl;
    }
    return 0;
}
cs


Comments