백준 17831 - 대기업 승범이네 (C++)

문제

• 문제 링크

  
   BOJ 17831 - 대기업 승범이네 
  

• 문제 요약

트리 형태의 회사 구조와, 각 직원의 실력 정보가 주어진다.
사수 - 부사수 관계에 놓인 직원들끼리 적절히 묶어 멘토링 관계를 만들어 줄 때,
모든 멘토링 관계에서 발생하는 시너지 합의 최댓값을 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$2 ≤ N ≤ 200,000$

$0 ≤ A_i ≤ 100$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 트리(trees)
• 트리에서의 다이나믹 프로그래밍(dp_tree)

풀이

직접적인 사수 - 부사수 관계에서만 멘토링 관계의 여부를 따질 수 있으므로, 임의의 노드(직원) $p$가 가질 수 있는 상태는 둘 중 하나다.

부모 노드(사수)와 멘토링 관계에 놓인 경우 $(q = 1)$

부모 노드(사수)와 멘토링 관계에 놓여있지 않은 경우 $(q = 0)$

첫 번째 경우라면 $p$는 아래로 이어진 노드(부사수)와 멘토링 관계를 형성할 수 없다. 즉, 선택의 여지가 없다.
두 번째 경우라면 $p$는 아래로 이어진 노드(부사수)와 멘토링 관계를 형성할 수도 있다. 즉, 선택의 여지가 있다.

이에 따라 다음과 같이 정의를 내려보자.

$dp[p][q] :$ $p$를 루트로 하는 서브 트리에서, $p$번 노드와 부모 노드의 멘토링 관계가 $q$일 때 시너지 합의 최댓값.

---

$p$와 부사수 관계에 놓인 노드들을 $k_1, k_2, ... k_i$라 할 때,

기본적인 점화식을 $dp[p][q] = Σdp[k_i][0]$ 으로 두고, $q$에 따라 나눠서 생각해보자.

$q == 1$

$p$와 $k_i$가 멘토링 관계에 놓이는 상황을 고려할 수 없다.
결국 기본 점화식을 그대로 따라가야 하므로,

$dp[p][q] = Σdp[k_i][0]$

$q == 0$

$p$와 $k_i$가 멘토링 관계에 놓이는 상황을 고려할 수 있다.
이땐 $dp[k_i][1]$의 값을 취해야 하고 시너지가 발생하므로,

$dp[p][q] = Σdp[k_i][0]$
$dp[p][q] = max(dp[p][q], max(dp[p][q] - dp[k_i][0] + dp[k_i][1] + A[p] * A[k_i]))$

자세한 흐름은 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
#define N 200001
using namespace std;
 
vector <int> Gr[N];
int a[N], dp[N][2];
 
void Init()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp);
    int n; cin >> n;
    for (int i(2), j; i <= n; i++)
        cin >> j, Gr[j].push_back(i);
    for (int i(1); i <= n; cin >> a[i++]);
}
int Solve(int p, int q, int o)
{
    int& t(dp[p][q]), s{};
    if (!~t)
    {
        t = 0;
        for (int& i : Gr[p])
            if (i ^ o)
                t = s += Solve(i, 0, p);
        if (!q)
            for (int& i : Gr[p])
                if (i ^ o)
                    t = max(t, s - dp[i][0] + Solve(i, 1, p) + a[p] * a[i]);
    }
    return t;
}
int main()
{
    Init();
    cout << Solve(1, 0, 0);
}

comment

끝