Hdu1520-Anniversary party(트리 dp)(시작 문제)

전송문: Anniversary party
제목: 회사 내의 직원 관계표는 하나의 나무로 모든 직원은 하나의 권한을 가진다. 연회를 열 때 한 직원과 그의 직속 상사는 동시에 나타날 수 없다(즉 직접 인접한 노드는 동시에 선택할 수 없다). 최대 권한을 구한다.
사고방식: 트리 dp 입문 문제.
노드 1을 루트로 선택하고 각 노드 u와 해당 서브노드 v에 대해 다음을 수행합니다.
노드 u를 선택하면 노드 v를 선택할 수 없습니다.
dp[u][1] += dp[v][0]
노드 u를 선택하지 않으면 노드 v의 공헌도가 큰 것을 선택한다(제목의 요구는 동시에 선택할 수 없고 당연히 동시에 선택하지 않을 수 있다).
dp[u][0] += max(dp[v][0], dp[v][1])
tips: 제목의 또 다른 구덩이는 여러 그룹의 데이터가 명확하게 밝혀지지 않았다는 것이다.

AC 코드:

#include 
#include 
#include 
using namespace std;
const int maxn=6e3+7;
struct node{
    int to,nxt;
}e[maxn*2];
int a[maxn],tot,head[maxn],dp[maxn][2];
void add(int u,int v){
    e[tot].nxt=head[u];
    e[tot].to=v;
    head[u]=tot++;
    return;
}
void add_edge(int u,int v){
    add(u,v);
    add(v,u);
    return;
}
void dfs(int rt,int p){
    for(int i=head[rt];~i;i=e[i].nxt){
        int to=e[i].to;
        if(to==p) continue;
        dfs(to,rt);
        dp[rt][1]+=dp[to][0];
        dp[rt][0]+=max(dp[to][0],dp[to][1]);
    }
    dp[rt][1]+=a[rt];
    return;
}
int main(void){
    int n;
    while(~scanf("%d",&n)){
        tot=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            dp[i][0]=dp[i][1]=0;
            head[i]=-1;
        }
        int u,v;while(~scanf("%d%d",&u,&v)){
            if(!u&&!v) break;
            add_edge(u,v);
        }
        dfs(1,0);
        printf("%d
",max(dp[1][0],dp[1][1]));
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

#4033. 맛있는 QQ(eat)

어느 날, 맛있는 QQ는 화성인에 의해 영문도 모른 채 수형국의 수도 루트로 전송되었다. 그 이름처럼 수형국은 바로 나무이다. 모두 n개 도시이고 n-1개의 길이 연결되어 도시와 도시 사이가 연결된다. 놀랍게도 QQ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Hdu1520-Anniversary party(트리 dp)(시작 문제)

좋은 웹페이지 즐겨찾기