[Baekjoon - 10763] Bessie's Birthday Buffet

난이도: Gold I

 

태그

• Dynamic Programming
• Breadth-First Search

 

풀이

1. 특정 Patch에서 멈추면서, 에너지를 최대로 하려면?

\( dp_{v} \) = \( v \)번 Patch에서 멈추면서, 받을 수 있는 최대 에너지 를 생각해봅시다.

 

저희는 Patch의 Quality가 증가하는 순서대로 이동할 것이므로, 점화식을 아래와 같이 써볼 수 있습니다.

\( dp_{v} = \max\limits_{Q_w < Q_v}(0, dp_{w} - E \cdot d_{v, w}) + Q_v \)

// 여기서 \( d_{v, w} \)는 \( v \)와 \( w \) 사이의 거리를 의미합니다.

 

\( N \) 제한이 작으니, \( O(N^2) \)에 DP를 구해줄 수 있습니다.

 

2. 모든 Patch 간의 거리는 어떻게 구할까?

일단 떠오르는 방법은 BFS를 \( N \)번 돌리는 것입니다. 하지만 이의 시간복잡도는 \( O(N+M) \)이죠.

최악의 경우에서, \( M = O(N^2) \)입니다.

 

하지만 이 문제에서는 정점의 차수가 10으로 제한되어있으므로, \( M = O(N) \)이 되어

시간복잡도가 \( O(N) \)이 됩니다.

그럼 BFS를 \( N \)번 돌려도 문제는 없겠죠.

 

3. 코드

vector<int> adj[1020];
 
const int INF = 0x3f3f3f3f;
int dis[1020][1020];
void bfs(int dis[1020], int st){
    memset(dis, 0x3f, sizeof(int)*1020); dis[st] = 0;
    //cout << "SET "; for (int i = 1; i <= 5; i++){ cout << dis[i] << ' '; } cout << endl;
    queue<int> q; q.push(st);
    while (!q.empty()){
        int now = q.front(); q.pop();
        //cout << "DIS " << st << ' ' << now << " = " << dis[now] << endl;
        for (int nxt : adj[now]){
            //cout << "CHK " << st << ' ' << now << ' ' << nxt << " = " << dis[now] << ' ' << dis[nxt] << endl;
            if (dis[nxt] <= dis[now]+1){ continue; }
            dis[nxt] = dis[now]+1; q.push(nxt);
        }
    }
}
inline void bfs(int st){ return bfs(dis[st], st); }
 
ll arr[1020]; pi2 srt[1020];
ll dp[1020];
 
void Main(){
    int n; ll x; cin >> n >> x;
    for (int v = 1; v <= n; v++){
        int k; cin >> arr[v] >> k;
        while (k--){
            int w; cin >> w; adj[v].push_back(w);
        }
        srt[v] = {arr[v], v};
    }
    for (int i = 1; i <= n; i++){ bfs(i); }
    sort(srt+1, srt+n+1);
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        int v = srt[i].sc;
        dp[v] = arr[v];
        for (int j = 1; j < i; j++){
            int w = srt[j].sc;
            dp[v] = max(dp[v], dp[w] - dis[v][w]*x + arr[v]);
        }
        ans = max(ans, dp[v]);
        //cout << "DP " << v << " = " << dp[v] << endl;
    }
    cout << ans;
}