[白俊]1949号:優秀村

9659 ワード
白駿 supin2 cpp テキストリンク
回答日:2021年10月03日

質問する


質問リンク:https://www.acmicpc.net/problem/1949

アクセスと解析


これはTreeでDPを利用して解決した問題である.
これはこの問題(に答える)に非常に類似した問題である.
この問題では、dp配列は以下のように定義される.
dp[a][0]=c:aノードが頂点であり,aが優秀村でない場合,優秀村住民数の最値である.
dp[a][1]=c:aノードが頂点であり,aが優秀村である場合,優秀村住民数の最値である.
これを使用してdfsにナビゲートする場合は、次の条件に注意して各ノードの状態を更新してください.
  • この村が優秀村である場合、次の村は必ずしも優秀村ではない.
  • この村が優秀村でなければ、次の村は優秀村でも優秀村でもない.
    △この場合、次の村が優秀村であれば、優秀村でなければ、2つの村の中で最高値を更新する.

    • コード#コード#

    // 백준 1949번 : 우수 마을
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> v[10001];
int resident[10001];
int dp[10001][2];
bool visited[10001];

void dfs(int node) {
    visited[node] = true;
    dp[node][0] = 0; // 해당 노드가 우수 마을이 아닐 경우
    dp[node][1] = resident[node]; // 해당 노드가 우수 마을일 경우

    for (int next : v[node]) {
        if (visited[next]) {
            continue;
        }
        dfs(next);
        dp[node][0] += max(dp[next][0], dp[next][1]);
        dp[node][1] += dp[next][0];
    }
}

int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> resident[i];
    }
    for (int i = 0, a, b; i < N - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);

    cout << max(dp[1][0], dp[1][1]);
    return 0;
}

    結果



    フィードバック


    似たような問題を解決すると、一定の概念があり、しかも面白いです.ほほほ
    [白俊]1003号-(Python Python)-Memorization
    centos 7 zookeeperをインストールし、起動を設定