글 읽기 - 1623번 질문

noru0114 4년 전 1

dp 점화식을 다음과 같이 정의하였습니다.

d[i][0] = i번째 사원이 root인 sub-tree에 대해 i번째 사원이 파티에 참여할 경우 날라리 분위기의 최댓값

d[i][1] = i번째 사원이 root인 sub-tree에 대해 i번째 사원이 파티에 참여하지 않을 경우 날라리 분위기의 최댓값

d[i][0] = sum( i 번째 사원의 직속부하직원 j들의 max(d[j][0], d[j][1] )

d[i][1] = sum( i 번째 사원의 직속부하직원 j들의 d[j][0], d[j][1]) + i의 날라리 분위기

문제에서 요구하는 날리리 분위기의 최대값은 구해지는것 같은데 참가자 번호들을 구하는 과정에서 막혀서 질문드립니다.

감사합니다.

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <time.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <bitset>
#include <list>

using namespace std;

int value[200000];
int boss[200000];
int d[200000][2];

vector<int> jjol[200000];

void dp_sol(int index)
{
	d[index][1] = value[index];
	
	for(int i=0;i<jjol[index].size();i++)
	{
		dp_sol(jjol[index][i]);
		if(d[jjol[index][i]][1] > d[jjol[index][i]][0])
			d[index][0] += d[jjol[index][i]][1];
		else
			d[index][0] += d[jjol[index][i]][0];
		d[index][1] += d[jjol[index][i]][0];
	}
	return;
}

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d", &value[i]);
	for(int i=1;i<n;i++)
	{
		int temp;
		scanf("%d", &temp);
		boss[i] = temp-1;
		jjol[boss[i]].push_back(i);
	}

	dp_sol(0);
	printf("%d %d\n", d[0][1], d[0][0]);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1623번 질문

noru0114 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말